Dlaczego nie jest to nierozstrzygalny problem w NP?

Najwyraźniej nie ma żadnych nierozstrzygalnych problemów w NP. Jednak według Wikipedii :

NP jest zbiorem wszystkich problemów decyzyjnych, dla których przypadki, w których odpowiedź brzmi „tak”, mają […] dowody, które są] weryfikowalne w czasie wielomianowym przez deterministyczną maszynę Turinga.

[...]

Mówi się, że problem występuje w NP wtedy i tylko wtedy, gdy istnieje weryfikator problemu, który wykonuje się w czasie wielomianowym.

Teraz rozważ następujący problem:

Biorąc pod uwagę równanie diofantyczne , czy ma jakieś rozwiązania liczb całkowitych?

Biorąc pod uwagę rozwiązanie, to łatwo zweryfikować w czasie wielomianowym, że tak naprawdę jest to rozwiązanie: wystarczy podłączyć numery do równania. Zatem problem tkwi w NP. Jednak rozwiązanie tego problemu jest znane z nierozstrzygalności !

(Podobnie wydaje się, że problem zatrzymania powinien dotyczyć NP, ponieważ rozwiązanie „tak” programu „zatrzymuje się na N-tym etapie” można zweryfikować na N krokach).

Oczywiście coś jest nie tak z moim rozumieniem, ale co to jest?

Równoważna definicja NP polega na tym, że obejmuje ona wszystkie problemy, które można rozstrzygać (a nie tylko weryfikować) w czasie wielomianowym przez niedeterministyczną maszynę Turinga. Wiadomo, że NTM nie mają większej mocy niż TM w tym sensie, że zestaw problemów rozstrzygalnych przez NTM jest identyczny z zestawem problemów rozstrzygalnych przez TM, więc wyraźnie z tej definicji nie może wynikać nierozstrzygalny problem w NP.

Aby wykazać, że dwie definicje NP są równoważne, biorąc pod uwagę istnienie deterministycznego weryfikatora, możesz wykazać, że istnieje niedeterministyczny decydent, i odwrotnie.

Załóżmy, że masz deterministyczny weryfikator wielomianowy. Jest też maszyna, która nie deterministycznie zgaduje certyfikat o długości ograniczonej wielomianem odpowiadającym wielkości certyfikatu związanej z tym problemem / weryfikatorem, a następnie uruchamia weryfikator. Ponieważ alfabet jest skończony, certyfikat dla dowolnego wejścia jest skończony (i co najwyżej wielomianowy w wielkości wejścia), a weryfikator działa w czasie wielomianowym, maszyna zatrzymuje się na wszystkich gałęziach dla wszystkich danych wejściowych i uruchamia się (inne niż deterministyczny) czas wielomianowy. Zatem dla każdego deterministycznego weryfikatora istnieje niedeterministyczny czynnik decydujący.

Jeśli masz niedeterministyczny decydent, to dla każdego obliczenia akceptującego możesz zapisać ścieżkę wyborów podejmowanych przez decydenta, aby osiągnąć stan akceptacji. Ponieważ decydujący działa w czasie wielomianowym, ścieżka ta będzie miała co najwyżej długość wielomianową. I deterministyczna TM łatwo jest zweryfikować, że taka ścieżka jest prawidłową ścieżką przez NTM do stanu akceptacji, więc takie ścieżki tworzą certyfikaty dla wielomianowego weryfikatora czasu dla problemu. Zatem dla każdego niedeterministycznego decydenta istnieje deterministyczny weryfikator.

Zatem żaden nierozstrzygalny problem nie może mieć weryfikatora, który działa na certyfikatach wielomianowych (w przeciwnym razie istnienie weryfikatora oznaczałoby istnienie decydującego).

Kiedy twierdzisz, że istnieje weryfikator dla problemu zatrzymania, certyfikat, o którym mówisz, to pewne kodowanie (TM, I, N), gdzie TM zatrzymuje się na wejściu I w N krokach. Można to rzeczywiście zweryfikować w krokach N, ale rozmiar certyfikatu nie jest wielomianowy w wielkości danych wejściowych (TM, I) do pierwotnego problemu (problem zatrzymania); N może być dowolnie duży (niezależnie od kodowania). Jeśli spróbujesz przekonwertować takiego weryfikatora na niedeterministyczny czynnik decyzyjny, uzyskasz dość interesującą maszynę. Powinieneś być w stanie udowodnić, że kiedy działa na (TM, I) dla TM, która tego nie robizatrzymaj na wejściu I nie ma żadnych ścieżek nie zatrzymujących się przez maszynę, ale także, że dla każdej ścieżki prowadzącej do stanu zatrzymania istnieje zawsze inna dłuższa ścieżka (odpowiadająca przypuszczeniu większej N), a zatem nie ma skończonego ograniczenia czas jego wykonania. Zasadniczo dzieje się tak, ponieważ istnieje nieskończona przestrzeń, którą należy zbadać na podstawie wstępnego niedeterministycznego domysłu. Przekształcenie takiego NTM w deterministyczną TM prowadzi do jednej z tych maszyn, które nie zapętlają się ani nie zatrzymują na niektórych danych wejściowych. W rzeczywistości nie istnieje żaden NTM, który mógłby rozstrzygnąć problem zatrzymania, dlatego nie ma weryfikatora działającego na certyfikatach o ograniczonym rozmiarze.

Nie znam się tak dobrze na równaniach diofantycznych, ale wygląda na to, że zasadniczo ten sam problem dotyczy twojego argumentu.

Z tego powodu łatwiej mi rozumować definicję NTM NP. Istnieją weryfikatory problemów, których nie można rozstrzygnąć (po prostu nie działają one na certyfikatach, które mają wielomianowy rozmiar związany z wielkością danych wejściowych do pierwotnego problemu). W rzeczywistości każdą TM, która rozpoznaje, ale nie decyduje o pewnym języku, można łatwo przekonwertować na weryfikator dla tego samego języka.

Jeśli myślisz o weryfikatorach, przypuszczam, że musisz wyznaczyć granice czasowe w odniesieniu do rozmiaru pierwotnego problemu , a nie do rozmiaru certyfikatu; możesz dowolnie zawyżać rozmiar certyfikatów, aby weryfikator działał w niższych terminach pod względem wielkości certyfikatu.

Myślę, że źle zrozumiałeś, co to znaczy rozwiązać równanie diofantyczne, i twierdzenie Matijasewicza o nierozstrzygalności .

$S$$f(n;x_1,...,x_k)$$n \in S$$x_1$$x_k$$f(n;x_1,...,x_k) = 0$. W szczególności problem zatrzymania jest typowym zestawem RE, więc rozwiązanie powyższego problemu jest nierozstrzygalne.

$x_1, ... x_k$

$x_1, ... , x_k$$n$$\log n$

$\mathsf{NP}$$p(N)$$N$$\mathsf{NP}$$p(N)$

Powinieneś przewinąć w dół do formalnej definicji :

$L$$p$$q$$M$

• $x$$M$$p(|x|)$$(x,y)$
• $x \in L$$y$$q(|x|)$$M(x,y) = 1$
• $x \not\in L$$y$$q(|x|)$$M(x,y) = 0$

Oznacza to, że weryfikator musi również pracować nad rozwiązaniami innymi niż rozwiązania. Gdzieś tam zawodzą nierozstrzygalne problemy (w twoim przypadku ograniczenie długości kandydatów do rozwiązania prawdopodobnie nie jest spełnione), co jest oczywiste dzięki (w sensie obliczalności) jaśniejszej definicji :

NP jest zbiorem problemów decyzyjnych rozstrzyganych przez niedeterministyczną maszynę Turinga, która działa w czasie wielomianowym.

Staram się podać więcej szczegółów dla powyższej odpowiedzi.

W rzeczywistości to pytanie stanowi problem dylematu.

Z jednej strony problem równania diofantycznego (DEP) jest nierozstrzygalny zgodnie z twierdzeniem Matiyesevicha (twierdzenie Matiyesevicha odpowiada na dziesiąty problem Hilberta, a problem Turinga uogólnia odpowiedź na uogólnienie dziesiątego problemu Hilberta, czyli Entscheidungsproblem); ale z drugiej strony nie ma nierozstrzygalnego problemu w NP zgodnie z definicją NP (rozstrzygalne i weryfikowalne).

To znaczy, że albo DEP nie ma w NP, albo DEP nie ma w NP. Oba dotyczą definicji NP.

Jeśli DEP nie występuje w NP, oznacza to, że problemy w NP (NDTM ＝ NonDeterminstic Turing Machine) są rozstrzygalne i weryfikowalne, to znaczy akceptujemy P = NP (NDTM).

Jeśli DEP jest w NP, to NP (NTM ＝ Non Turing Machine) zawiera rozstrzygalne i nierozstrzygalne, oczywiście rozstrzygalne jest weryfikowalne, dlatego problem polega na tym, czy nierozstrzygalne jest weryfikowalne? W rzeczywistości jest to znany problem P vs. NP. Z pewnością nierozstrzygalność jest niemożliwa do zweryfikowania, więc NP odpowiada NTM (Maszyna nie Turinga) zamiast NDTM (Maszyna Turinga NonDeterminstic).

Opierając się na założeniu, że DEP jest w NP (NTM), uważamy, że NP (NTM) jest problemem niedeterministycznym (nierozstrzygalnym), a obecna definicja NP (NDTM, rozstrzygalna i weryfikowalna) straciła ten niedeterminizm (nierozstrzygalny), więc uważamy, że należy go przesłuchać.

Uważamy, że dylemat, który poruszyłeś na temat równania diofantycznego, jest bardzo znaczący, ponieważ ujawnia coś nienormalnego w obecnej definicji NP: - Mówi się, że problem występuje w NP wtedy i tylko wtedy, gdy istnieje weryfikator problemu, który występuje w wielomianu czas.

Jeśli chodzi o definicję NP, można ją prześledzić do lat 60-tych, w których odkryto dużą liczbę odpowiednich i znaczących problemów, dla których nie można było znaleźć algorytmów wielomianowych do ich rozwiązania, aby rozpoznać te problemy na podstawie problemów rozwiązanych w czasie wielomianowym (P), koncepcja NP została przedstawiona.

Jednak obecna definicja NP zdefiniowana jako weryfikowalna w czasie wielomianowym myli NP z P, ponieważ problem w P jest również weryfikowalny w czasie wielomianowym. Innymi słowy, taka definicja prowadzi do utraty esencji NP, „nondeterminisme”. W konsekwencji powoduje to poważne niejasności w zrozumieniu NP, na przykład twój dylemat: z natury problem równania diofantycznego jest nierozstrzygalny; ale z definicji NP jest rozstrzygalne,…

Naszym zdaniem trudność w rozwiązaniu „P kontra NP” leży przede wszystkim na poziomie poznawczym, więc jeśli mamy nadzieję uzyskać wgląd w „P kontra NP”, najpierw musimy zadać pytanie: co to jest NP?