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

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?

complexity-theory np

— Drozi
źródło

Być może źle zrozumiałem, ale dlaczego nie jest to algorytm weryfikacji czasu wielomianowego? Biorąc pod uwagę

, samodzielnie oblicz funkcję

, używając algorytmu czasu wielomianowego, i zwróć „poprawne”, jeśli

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

$(x,y)$

f (x)

$f(x)$

f (x) = y

$f(x)=y$

— Lieuwe Vinkhuijzen,

@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:

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 , produkujemy inną TM tak że i (gdzie oznacza kodowanie (liczba Gödla) na Liczba naturalna) $n \in \mathbb{N}$ $M$ $N$ $L(M)=L(N)$ $\# N > n$ $\# N$ $N$

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 . Jest to podstawowe, powtarzające się zastosowanie Padding Lemma na bazach TM. Będzie to wymagało wypełnień, z których każdy może dodać jeden stan, a zatem można to zrobić w czasie wielomianowym. $M$ $n$ $n$

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

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ę (w jedności), obliczenie wykresu zawierającego klikę jest banalne . Ale biorąc pod uwagę trudno jest sprawdzić, czy istnieje klika. $L(M)=L(N)$ $n$ $G$ $n$ $n,G$ $n$

— chi
źródło

Spodziewałem się, że tak nie będzie. Świetna odpowiedź!

— Filip Haglund,

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ę,

, to jest łatwe do sprawdzenia, czy

daje maszynie

. Bez

pytaniem jest, czy łatwo jest wygenerować twarde wystąpienia języków (NPC), co jest prawdą tylko w Minicrypt i Cryptomania.

z

$z$

M, N

$M, N$

z

$z$

z

$z$

M

$M$

z

$z$

— Lieuwe Vinkhuijzen,

@chi Nie wszystkie pary

mogą być certyfikowane, ale zestaw par

wygenerowany przez twój algorytm może być certyfikowany. Certyfikat jest transkrypcją twojego algorytmu produkującego

(np. „Zacznij od

, następnie dodaj ten stan i dodaj to przejście, a następnie ... i voilà,

!”). Ogólnie rzecz biorąc, jeśli

jest niedeterministycznym algorytmem, który przy danym

zawsze oblicza dopuszczalne

, to transkrypcja ścieżki obliczeniowej

jest certyfikatem, że dane

jest dopuszczalne.

M, N

$M, N$

M, N

$M, N$

N

$N$

M

$M$

M

$M$

N

$N$

T

$T$

x

$x$

y

$y$

T (x)

$T(x)$

y

$y$

— Lieuwe Vinkhuijzen,

@chi W pytaniu pojawia się niewielka niuans: w przypadku arbitralnej relacji

możliwe jest, że nie wszystkie dopuszczalne

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.

R

$R$

y

$y$

— Lieuwe Vinkhuijzen,

@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 ? $NP\subsetneq P$ ” (nie).

— Lieuwe Vinkhuijzen,

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:

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