Dlaczego nie jest to nierozstrzygalny problem w NP?

25

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?

BlueRaja - Danny Pflughoeft
źródło
1. Pamiętaj, że cytowana definicja dotyczy problemów decyzyjnych. 2. Jeśli chodzi o twój przykład diofantyny, nie twierdzisz, że każdy system istnieje wielomian związany z rozmiarem rozwiązań, prawda?
Dmitrij Chubarow,
@Dmitri: Er, tak twierdzę. Rozmiar rozwiązania jest dokładnie taki sam jak rozmiar problemu - jeśli występuje N niewiadomych, rozwiązanie zawiera N liczb całkowitych. I to jest problem decyzyjny - rozwiązaniem na liczbę całkowitą (potrzebną do zweryfikowania przypadku „tak”) byłby jego certyfikat .
BlueRaja - Danny Pflughoeft
19
Pytanie brzmi, jak duże są intryganci
Artem Kaznatcheev
10
@ BlueRaja-DannyPflughoeft, jeśli masz nieskończony alfabet do kodowania liczb całkowitych, nie jesteś już w standardowym ustawieniu teorii złożoności. W przypadku skończonego alfabetu rozmiar kodowania rośnie wraz z wartością liczby całkowitej.
Dmitrij Chubarow
Rozwiązanie problemu zatrzymania zwróciłoby po prostu „Tak”, bez wskazania liczby kroków do symulacji w celu weryfikacji.
RemcoGerlich,

Odpowiedzi:

10

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.

Ben
źródło
26

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

Sf(n;x1,...,xk)nSx1xkf(n;x1,...,xk)=0. W szczególności problem zatrzymania jest typowym zestawem RE, więc rozwiązanie powyższego problemu jest nierozstrzygalne.

x1,...xk

x1,...,xknlogn

NPp(N)NNPp(N)

Artem Kaznatcheev
źródło
Oczywiście rozumiem, co to znaczy „rozwiązać równanie diofantyczne” - znajdziesz liczby, które spełniają to równanie. Nie rozumiem, dlaczego twierdzenie o nierozstrzygalności Matiyasevicha lub rekurencyjnie wyliczalne zbiory muszą zostać włączone do dyskusji. Ale myślę, że ostatni akapit mógłby to wyjaśnić ...
BlueRaja - Danny Pflughoeft
1
W porządku, ta nowa edycja wyjaśnia to - to także wyjaśnia, dlaczego problemu zatrzymania nie ma w NP, ponieważ kroki, które należy podjąć, aby się zatrzymać, mogą być dowolnie duże. Dzięki!
BlueRaja - Danny Pflughoeft
Moją sugerowaną edycją było usunięcie dwóch pierwszych akapitów. Dwa pierwsze akapity wyjaśniają, dlaczego 10. problem Hilberta jest nierozstrzygalny, co jest całkowicie styczne do pytania; po prostu odwracają uwagę od reszty odpowiedzi (w przeciwnym razie jest to świetna odpowiedź!) .
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft, jeśli pierwszy akapit cię obraził, to mogę go usunąć (chociaż pytałeś „co jest nie tak z moim zrozumieniem?”). Drugi akapit jest konieczny, aby sformalizować problem bardziej formalnie, ponieważ nie ma go w pytaniu.
Artem Kaznatcheev
3
@ BlueRaja-DannyPflughoeft Najlepiej, jeśli pytania i odpowiedzi są samodzielne. Mój drugi akapit przedstawia problem i wyjaśnia, co to znaczy, że ten problem jest nierozstrzygalny. Mój trzeci akapit daje szybką odpowiedź. Mój czwarty i piąty akapit omawiają to bardziej szczegółowo. O ile mogę stwierdzić, wszystkie akapity są konieczne.
Artem Kaznatcheev
8

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

LpqM

  • xMp(|x|)(x,y)
  • xLyq(|x|)M(x,y)=1
  • xLyq(|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.

Raphael
źródło
„weryfikator musi działać także na nierozwiązania” - jeśli mówisz, że weryfikator musi zawieść w przypadku nierozwiązań, to już działa. Jeśli twierdzisz, że weryfikator musi być w stanie zweryfikować odpowiedzi „nie”, jest to niepoprawne - byłoby to co-NP . I już zdaję sobie sprawę z drugiej definicji, ale byłem zdezorientowany, w jaki sposób może ona być równoważna z pierwszą, ponieważ jedna definicja wydaje się dopuszczać problem w pytaniu, a druga nie.
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPlughoeft: Moje spostrzeżenie jest następujące: weryfikatorzy muszą być w stanie obalić nierozwiązane rozwiązania. Jeśli jesteś tego świadomy, edytuj odpowiednio swoje pytanie; sprawia, że ​​wyglądasz zupełnie nieświadomie.
Raphael
To oczywiste, że weryfikator obala już nierozwiązania: wystarczy podłączyć liczby do równania i sprawdzić, czy się trzyma. Obawiam się, że nie rozumiem, do czego próbujesz się dostać.
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPlughoeft: Cytowana „definicja” nie określa tego zachowania.
Raphael
-1

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ć.

Yu Li
źródło
1
Nie, nierozstrzygalność DEP (dziesiąty problem Hilberta) została pokazana dopiero w 1970 roku przez Matiyesevicha. Entscheidungsproblem nie jest dziesiątym problemem Hilberta; dotyczy ważności formuł logiki pierwszego rzędu. I jeszcze raz problem P vs. NP absolutnie nie stanowi problemu, czy problemy nierozstrzygalne są możliwe do zweryfikowania.
David Richerby,
1
Jeśli chcesz podać więcej szczegółów, edytuj swój oryginalny post.
Tom van der Zanden,
@DavidRicherby Zauważ, że odpowiedź udzielona przez Bena: „zbiór problemów rozstrzyganych przez NTM jest identyczny z zestawem problemów rozstrzyganych przez TM”. Właśnie w tym sensie myślę, że definicja NP myli P z NP i prowadzi do P = NP (NDTM). Jeśli definicja ta musi zostać zakwestionowana, należy również zakwestionować inne wnioski wynikające z tej definicji, takie jak równoważność deterministycznego weryfikatora i niedeterministycznego decydenta.
Yu Li
@YuLi „prowadzi do P = NP (NDTM).” Nie mam pojęcia, co przez to rozumiesz. Nie widzę też znaczenia, aby zwracać uwagę, że bazy TM i NTM decydują o tych samych językach. Gdyby nie zdecydowali się na te same języki, NTM byłyby całkowicie nieracjonalnym modelem obliczeń i trudno sobie wyobrazić, że zależy nam na tym, co mogą obliczyć w czasie wielomianowym. W teorii złożoności zajmujemy się bardziej szczegółowym poglądem i pytamy o wymagane zasoby obliczeniowe, a definicja NP w ogóle tego nie myli.
David Richerby
@DavidRicherby Dzięki, zmodyfikowałem moją odpowiedź zgodnie z twoją uwagą, aby wyjaśnić związek Entscheidungsproblem i dziesiątego problemu Hilberta. Jeśli chodzi o pytanie dotyczące obecnej definicji NP, trudno jest omówić go kilkoma słowami. Celem mojej odpowiedzi jest wywołanie refleksji na temat tego podstawowego tematu…
Yu Li
-2

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?

Yu Li
źródło
4
Wydaje się, że jest to opinia na temat definicji NP , a nie odpowiedź na pytanie. Definicja NP jest w porządku. Nie myli P z NP ; raczej uznaje, że P jest podzbiorem NP . Dla mnie byłoby bardzo nienaturalne, gdyby P nie był podzbiorem NP . NP to klasa problemów, które można rozwiązać w określonych granicach zasobów. To z konieczności obejmuje całą masę łatwych problemów ( P ), które można rozwiązać bez zbliżania się do limitu dostępnych zasobów.
David Richerby
@DavidRicherby P i NP mają wspólną właściwość „certyfikatu weryfikowalnego w czasie wielomianowym”, ale ta właściwość nie jest istotą NP. Jeśli ta właściwość jest używana do zdefiniowania NP, wówczas P jest podzbiorem NP, a NP ma P jako swój podzbiór (rozstrzygalny) i sam w sobie (nierozstrzygalny). Dlatego zastanawiasz się, czy NP jest rozstrzygalne, czy nierozstrzygalne? Podobnie jak powyższy dylemat: czy równanie diofantyczne jest nierozstrzygalne, czy rozstrzygalne? Więc moją odpowiedzią jest zasugerowanie zbadania tego dylematu z punktu widzenia definicji NP: weryfikowalny, nierozstrzygalny jest niemożliwy do zweryfikowania!
Yu Li
Problemy NP są rozstrzygalne definicji: NP jest klasa problemów zdecydowały o niedeterministycznych maszyny Turinga. Łatwo jest udowodnić, że jest to dokładnie ten sam zestaw problemów, które mają certyfikaty wielomianowe, które można zweryfikować w czasie wielomianowym. Jeśli martwisz się, że problemy w NP mogą nie być rozstrzygalne, to coś źle zrozumiałeś.
David Richerby
Tak, martwię się, że problemy w NP mogą nie być rozstrzygalne. Mówisz o równoważności dwóch definicji NP: NP jest klasą problemów ustalanych przez niedeterministyczne maszyny Turinga; NP to klasa problemów z weryfikacją certyfikatów wielomianowych w czasie wielomianowym. Wątpię w tę równoważność, ponieważ jedna dotyczy istnienia algorytmu do rozwiązania problemu, a druga dotyczy istnienia rozwiązania problemu. Dylemat dotyczący równania diofantycznego może być bezpośrednio związany z tą równoważnością (zobacz więcej szczegółów mojego argumentu: arxiv.org/abs/1501.01906 ).
Yu Li
2
@YuLi Równoważność dwóch definicji NP jest tak prosta, że ​​uczy się jej w klasach teorii złożoności studentów. Sugeruję, aby nie przesyłać plików do ArXiv, jeśli nie rozumiesz podstaw tej dziedziny.
David Richerby