Czy istnieje zadanie, które można rozwiązać w czasie wielomianowym, ale którego nie da się zweryfikować w czasie wielomianowym?

34

Mój kolega i ja właśnie uderzyliśmy w notatki jednego z naszych profesorów. Notatki stwierdzają, że istnieją zadania, które można rozwiązać w czasie wielomianowym (są w klasie PF), ale NIE są możliwe do zweryfikowania w czasie wielomianowym (NIE są w klasie NPF).

Aby rozwinąć te klasy: Otrzymujemy trochę danych wejściowych X i tworzymy dane wyjściowe Y tak, że (X, Y) są w relacji R reprezentującej nasze zadanie. Jeśli możliwe jest uzyskanie Y dla X w czasie wielomianowym, zadanie należy do klasy PF. Jeśli jest możliwe zweryfikowanie wielomianowego certyfikatu Z, który dowodzi, że krotka (X, Y) jest w relacji R w czasie wielomianowym, zadanie należy do klasy NPF.

Nie mówimy o problemach decyzyjnych, gdzie odpowiedź brzmi TAK lub NIE (bardziej formalnie, jeśli jakiś ciąg należy do jakiegoś języka). W przypadku problemów decyzyjnych wydaje się, że PF jest właściwym podzbiorem NPF. Jednak w przypadku innych zadań może być inaczej.

Czy znasz zadanie, które można rozwiązać w czasie wielomianowym, ale nie zweryfikować w czasie wielomianowym?

Drozi
źródło
8
Być może źle zrozumiałem, ale dlaczego nie jest to algorytm weryfikacji czasu wielomianowego? Biorąc pod uwagę , samodzielnie oblicz funkcję f ( x ) , używając algorytmu czasu wielomianowego, i zwróć „poprawne”, jeśli f ( x ) = y . Czy to możliwe, że źle odczytałeś lub profesor źle napisał i chciał zamiast tego powiedzieć, że istnieją problemy, które można zweryfikować w czasie wielomianowym, ale których nie można rozwiązać w czasie wielomianowym? (x,y)f(x)f(x)=y
Lieuwe Vinkhuijzen,
1
@LieuweVinkhuijzen „powiedzieć, że istnieją problemy, które można zweryfikować w czasie wielomianowym, ale których nie można rozwiązać w czasie wielomianowym?” [ref. potrzebne]
T. Verron,
@ T.Verron Haha tak, ja też byłbym bardzo szczęśliwy widząc dowód profesora na to twierdzenie;)
Lieuwe Vinkhuijzen,

Odpowiedzi:

44

Jest to możliwe tylko wtedy, gdy istnieje wiele dopuszczalnych wyjść dla danego wejścia. To znaczy , gdy relacja nie jest funkcją, ponieważ narusza wyjątkowość.R

Rozważmy na przykład ten problem:

Biorąc pod uwagę (reprezentowane jako unarne) i TM M , produkujemy inną TM N, tak że L ( M ) = L ( N ) i # N > n (gdzie # N oznacza kodowanie (liczba Gödla) N na Liczba naturalna)nNMNL(M)=L(N)#N>n#NN

Rozwiązanie tego jest trywialne: dodawaj kilka nadmiarowych stanów do TM , być może z pewnymi przejściowymi przejściami między nimi, dopóki kodowanie nie przekroczy n . Jest to podstawowe, powtarzające się zastosowanie Padding Lemma na bazach TM. Będzie to wymagało n wypełnień, z których każdy może dodać jeden stan, a zatem można to zrobić w czasie wielomianowym.Mnn

Z drugiej strony, biorąc pod uwagę jest nierozstrzygalny, aby sprawdzić, czy N jest prawidłowe wyjście dla wejść n , M . Rzeczywiście, sprawdzenie L ( M ) = L ( N ) jest nierozstrzygalne (zastosuj twierdzenie Rice'a), a ograniczenie # N > n odrzuca tylko wiele N z nich. Ponieważ usuwamy skończoną liczbę elementów z nierozstrzygalnego problemu, nadal mamy problem nierozstrzygalny.n,M,NNn,ML(M)=L(N)#N>nN

Można również zastąpić niezdecydowaną właściwość aby uzyskać warianty, które są nadal obliczalne, ale NP trudne / pełne. Np. Biorąc pod uwagę n (w jedności), obliczenie wykresu G zawierającego n- klikę jest banalne . Ale biorąc pod uwagę n , G trudno jest sprawdzić, czy istnieje n- klika.L(M)=L(N)nGnn,soln

chi
źródło
1
Spodziewałem się, że tak nie będzie. Świetna odpowiedź!
Filip Haglund,
7
To nie odpowiada na pytanie. OP konkretnie poprosił o problem niemożliwy do zweryfikowania w zwykłym znaczeniu, w którym oprócz danych wejściowych i rzekomej odpowiedzi otrzymujemy certyfikat który poświadcza poprawność odpowiedzi. W twoim przypadku certyfikat to bity użyte do niedeterministycznego wygenerowania nowej równoważnej Maszyny Turinga. Biorąc pod uwagę, M , N i Z , to jest łatwe do sprawdzenia, czy oo daje maszynie M . Bez z pytaniem jest, czy łatwo jest wygenerować twarde wystąpienia języków (NPC), co jest prawdą tylko w Minicrypt i Cryptomania. zM,NzzMz
Lieuwe Vinkhuijzen,
2
@chi Nie wszystkie pary mogą być certyfikowane, ale zestaw par M , N wygenerowany przez twój algorytm może być certyfikowany. Certyfikat jest transkrypcją twojego algorytmu produkującego N z M (np. „Zacznij od M , następnie dodaj ten stan i dodaj to przejście, a następnie ... i voilà, N !”). Ogólnie rzecz biorąc, jeśli T jest niedeterministycznym algorytmem, który przy danym x zawsze oblicza dopuszczalne y , to transkrypcja ścieżki obliczeniowej T ( x ) jest certyfikatem, że dane y jest dopuszczalne.M,NM,NNMMNTxyT(x)y
Lieuwe Vinkhuijzen,
3
@chi W pytaniu pojawia się niewielka niuans: w przypadku arbitralnej relacji możliwe jest, że nie wszystkie dopuszczalne y są możliwe do poświadczenia, a Ty podajesz elegancki przykład. Jednak pytanie nie pyta, czy dopuszczalne ale uncertifiable stosunki istnieją (odpowiedź brzmi tak , by swoim przykładzie), a nie pyta, czy możemy mieć algorytm, który wytwarza dopuszczalny, uncertifiable wyjście. Odpowiedź, tu musi być nie z powodu argument powyżej. Ry
Lieuwe Vinkhuijzen,
2
@chi Nie wiem, o co chciał zapytać OP, ale Twoja odpowiedź była bardzo pouczająca, ale nauczyłem się czegoś! imo pytanie można odczytać tak, jak to robisz, lub równie prawdopodobne, że „ czy istnieją funkcje jednokierunkowe? ” (może) lub „ czy trudne są problemy z NP do wygenerowania? ” (mam nadzieję, że w przypadku RSA), lub, sposób, w jaki go czytam, jako „ Czy ?NPP ” (nie).
Lieuwe Vinkhuijzen,
1

Jest to jedynie rozwinięcie pierwszego zdania odpowiedzi @ chi, ponieważ nie uważałem tego za oczywiste.

Chodzi o to, że jeśli masz algorytm, który znajduje odpowiedź na jakiś problem w czasie wielomianowym, istnieją dwie możliwości:

  1. Wcześniej udowodniono (matematycznie), że dane wyjściowe algorytmu są rozwiązaniem problemu, w którym to przypadku same kroki algorytmu stanowią dowód poprawności.

  2. Masz inny algorytm do sprawdzania, czy dane wyjściowe są rzeczywiście rozwiązaniem, w którym to przypadku musisz uruchomić ten algorytm (w przeciwnym razie byłbyś objęty przypadkiem nr 1), co oznacza, że ​​robisz to w czasie wielomianowym.

Dlatego nie może być takiego problemu.

Mehrdad
źródło
Nie rozumiem # 2. Co oznacza, że ​​inny algorytm działa w czasie wielomianowym?
Albert Hendriks,
@AlbertHendriks: Jeśli weryfikator nie działał w czasie wielomianowym, oryginalny solver nie mógł twierdzić, że znalazł prawidłowe rozwiązanie w czasie wielomianowym, ponieważ musi uruchomić weryfikator, aby upewnić się, że jego rozwiązanie jest poprawne.
Mehrdad,