Jaka jest różnica między „decyzją” a „weryfikacją” w teorii złożoności?

W teorii obliczeń Michaela Sipsera na stronie 270 pisze:

P = klasa języków, dla których członkostwo można szybko ustalić.
NP = klasa języków, dla których członkostwo można szybko zweryfikować.

Jaka jest różnica między „zdecydowanym” a „zweryfikowanym”?

Zadaniem decydującym o członkostwie jest: biorąc pod uwagę dowolne dane wejściowe , zdecyduj, czy x ∈ L , tj. Obliczyć następującą funkcję:$x$$x \in L$

$\qquad \displaystyle \chi_L(x) = \begin{cases}1 &x \in L \\ 0 & x\notin L\end{cases}$

Z drugiej strony, zadaniem weryfikacji członkostwa jest: biorąc pod uwagę wszelkie dane wejściowe i (proponowany) dowód (lub świadek ) członkostwa, szybko sprawdź czy x ∈ L tym dowodem ¹.$x$$x\in L$

Rozważmy na przykład rozkład na czynniki pierwsze. Biorąc pod uwagę , oblicz wszystkie czynniki pierwsze n . Z drugiej strony, biorąc pod uwagę ( n , { i 1 , … , i k } ) , sprawdź, czy ∏ k j = 1 i j = n . Co jest łatwiejsze?$n \in \mathbb{N}$$n$$(n, \{i_1, \dots, i_k\})$$\prod_{j=1}^k i_j = n$

Inny przykład: Biorąc pod uwagę wykres ważony , zdecyduj, czy istnieje koło Hamiltona (które odwiedza wszystkie węzły) o wadze co najwyżej k . Z drugiej strony, biorąc pod uwagę ( G , ( v 1 , … , v n ) ) , sprawdź, czy ścieżka v 1 → ⋯ → v n odwiedza wszystkie węzły dokładnie raz i ma masę co najwyżej k . Co jest trudniejsze?$G = (V,E)$$k$$(G, (v_1, \dots, v_n))$$v_1 \to \dots \to v_n$$k$

1. Więc powiesz „nie”, jeśli ale dowód jest błędny. W porządku, ponieważ rozważamy niedeterministyczne maszyny w tym kontekście; ważne jest tylko, abyśmy mogli odgadnąć prawidłowy dowód i zweryfikować go (szybko).$x \in L$

Jeśli zignorujemy problemy z wydajnością, istnieje inny przykład, który ilustruje różnicę przez analogię. Wiemy, że problem zatrzymania nie jest rozstrzygalny: biorąc pod uwagę kod dla maszyny Turinga, nie ma skutecznego sposobu na ustalenie, czy maszyna zatrzymuje się, jeśli jest uruchomiona bez danych wejściowych.$e$

Ale jeśli maszyna się zatrzyma, nie jest trudno udowodnić komuś innemu: po prostu powiedz jej, ile kroków maszyna wykonuje , zanim się zatrzyma. Mogą uruchomić maszynę na tyle kroków i wiedzieć, czy powiedziałeś prawdę (oczywiście ignorując wydajność).

Tak więc zestaw zatrzymujących się maszyn Turinga nie jest rozstrzygalny, ale jest weryfikowalny. Pamiętaj, że nie trzeba przedstawiać dowodów na maszyny, które się nie zatrzymują. Weryfikacja jest asymetryczna w tym sensie, że tylko członkostwo w zestawie ma być weryfikowalne, członkostwo poza zestawem nie.

Sytuacja z P i NP jest analogiczna. Język znajduje się w NP, jeśli istnieje system dowodów, dzięki czemu każdy obiekt w tym języku ma krótki dowód (ograniczony wielomianem w rozmiarze obiektu), który można skutecznie zweryfikować (za pomocą szeregu kroków ograniczonych przez wielomian wielkości wejścia).

Z drugiej strony, język znajduje się w P, jeśli istnieje sposób na stwierdzenie, czy dowolny obiekt jest w języku, czy nie, przy użyciu szeregu kroków ograniczonych wielomianem wielkości obiektu. Teraz musimy się martwić o arbitralne dane wejściowe, a nie tylko obiekty w języku. Ale ten problem jest symetryczny: jeśli język jest w P, to i jego dopełnienie. Pytanie, czy dopełnienie każdego języka NP jest również językiem NP, pozostaje nierozwiązane.

(Ta analogia sugeruje, że problemy NP dotyczą problemów P, takich jak zbiory re są zestawami obliczalnymi. To jest trochę prawda, ale może być mylące. Jest to podstawowy fakt, że zbiór, który jest re i co-re, jest obliczalny, podczas gdy nie wiadomo, czy każdy zestaw, który jest NP i Co-NP jest w P).