Wada mojego NP = dowód CoNP?

Mam ten bardzo prosty „dowód” na NP = CoNP i myślę, że gdzieś coś zrobiłem źle, ale nie mogę znaleźć, co jest nie tak. Czy ktoś może mi pomóc?

Niech A będzie pewnym problemem w NP, i niech M będzie decydującym dla A. Niech B będzie dopełnieniem, tj. B jest w CoNP. Ponieważ M jest decydującym, możesz go również użyć, aby zdecydować B (po prostu odwróć odpowiedź). Czy to nie znaczy, że rozwiązujemy zarówno problemy NP, jak i CoNP za pomocą tego samego M?

Mówiąc bardziej konkretnie.

Niech A będzie problemem NP-zupełnym, i niech M będzie decydował o A. Rozważmy każdy problem B w CoNP. Rozważamy jego uzupełnienie nie-B, które jest w NP, a następnie uzyskujemy redukcję wielomianową do A. Następnie uruchamiamy nasz decydujący M i odwracamy naszą odpowiedź. W ten sposób uzyskujemy czynnik decydujący dla B. Oznacza to, że B również występuje w NP.

Czy mogę wiedzieć, co jest nie tak z moim rozumowaniem?

Istnieją dwa możliwe błędy w tym dowodzie:

1. Kiedy mówisz „decydujący” - masz na myśli deterministyczną TM. W tym przypadku najlepiej po polsku (według naszej wiedzy) z automatyczną NP do deterministycznej maszyny mogą dostarczyć maszynę, która przebiega w wykładniczej czasu, więc po uzupełnieniu trzeba będzie decydującym dla dopełnienia w wykładniczym czasie, udowadniając, że (lub, po pewnej optymalizacji, c o - N P ⊆ P S P A C E ).$co-NP\subseteq EXP$$co-NP\subseteq PSPACE$

2. Kiedy mówisz „decydujący”, masz na myśli niedeterministyczną TM. W takim przypadku odwrócenie odpowiedzi niekoniecznie uzupełni język. Rzeczywiście, językiem odwróconej maszyny będą wszystkie słowa, dla których istnieje odrzucająca seria na $M$$w$

Oto inny sposób patrzenia na punkt, który Shaull robi w odniesieniu do „decydentów”.

Problem występuje w NP wtedy i tylko wtedy, gdy istnieje algorytm taki, że$V: \{0,1\}^n \times \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}$

• dla każdej instancji TAK , istnieje certyfikat p ∈ { 0 , 1 } p o l y ( n ) taki, że V ( x , p ) = 1 ; i$x \in \{0,1\}^n$$p \in \{0,1\}^{\mathrm{poly}(n)}$$V(x,p) = 1$

• dla każdego wystąpienia NO mamy V ( x , p ) = 0 dla wszystkich p ∈ { 0 , 1 } p o l y ( n ) .$x \in \{0,1\}^n$$V(x,p) = 0$$p \in \{0,1\}^{\mathrm{poly}(n)}$

Są one zwykle określane jako kompletności i kondycji finansowej warunków NP algorytm weryfikacja: „kompletność” warunek mówi, że każdy przypadek TAK posiada certyfikat, a „solidność” warunek mówi, że algorytm nie jest oszukiwany przez instancję NO. W przypadku koNP jest odwrotnie: istnieje algorytm weryfikujący, który zaakceptuje co najmniej jeden certyfikat dla dowolnej instancji NIE, ale której nigdy nie da się oszukać przez instancję TAK.

Jeśli chcesz, aby pokazać, że NP ⊆ CONP , trzeba pokazać, że każde NP problem ma CONP -type weryfikator, które mogą poświadczyć NO instancji zamiast instancji Tak. Nie można tego zrobić za pomocą niedeterministycznej maszyny Turinga: nie wiemy na przykład, jak skutecznie mapować instancje SAT względem siebie, w taki sposób, że wszystkie niezadowalające formuły są odwzorowywane na satysfakcjonujące i odwrotnie. (Negowanie wyników formuły nie wystarczy, na przykład: formuła, która jest zadowalająca, ale nie tautologia, zostałaby po prostu zmapowana na inną formułę, która była zadowalająca, ale nie tautologię, gdy zamiast tego potrzebowalibyśmy formuły niezadowalającej.) Po prostu nie ma sposobu, aby oszukać „niedeterministyczną maszynę” w wykrywaniu czegoś takiego, jak wszystkie ścieżki odrzucające.

Możesz zapytać: „Czy niedeterministyczna maszyna Turinga nie wie, jaki uzyska wynik?” Odpowiedź brzmiałaby nie , nie ma. Działanie maszyny niedeterministycznej nie daje jej dostępu do żadnych informacji o więcej niż jednej ścieżce obliczeniowej naraz: możesz pomyśleć, że działa ona na wielu ścieżkach równolegle, ale w obrębie każdej ścieżki wie tylko o tej jednej ścieżce. Jeśli spróbujesz wyposażyć go w możliwość „uświadomienia sobie”, czy istnieją jakieś rozwiązania, to zamiast tego opisujesz maszynę z wyrocznią NP , która jest bardziej (potencjalnie!) Silniejsza niż prosta niedeterministyczna maszyna Turinga.

• Na przykład, jeśli wyposażyć (deterministyczny) Maszyna Turinga z NP wyroczni, to problemy, które można rozwiązać w czasie wielomianowym na tym komputerze nazywa , który jest często napisane P N P . „Wyrocznia” pozwala maszynie po prostu odbierać odpowiedzi na problemy z NP zakończone w jednym kroku, a więc P N P oczywiście zawiera P ; a ponieważ możesz zanegować odpowiedzi, to oczywiście zawiera również CoNP . Ale nie wiemy, czy przechowuje się odwrotna zawartość, właśnie dlatego, że nie wiemy, jak oszukać niedeterministyczne maszyny Turinga w wykrywaniu BRAK odpowiedzi.$\Delta_2^{\mathrm P}$$\mathsf{P}^{\mathsf{NP}}$$\mathsf{P}^{\mathsf{NP}}$

• Co więcej, jeśli dasz niedeterministycznej maszynie Turinga możliwość uświadomienia sobie wyniku problemu w NP , problemy, które ta maszyna może rozwiązać w czasie wielomianowym, nazywa się lub N P N P , i to powszechnie uważa się, że jest ściśle większy niż klasa P N P . Zawiera również NP i coNP - ale podobnie jak NP , nie wiadomo, że jest zamykane w ramach uzupełnień: niedeterministyczna maszyna wyroczni może wiedzieć, kiedy problem w NP$\Sigma_2^{\mathrm P}$$\mathsf{NP}^{\mathsf{NP}}$$\mathsf{P}^{\mathsf{NP}}$nie ma odpowiedzi NIE z powodu wyroczni, ale nadal utknąłby w działaniu w jednej ze swoich (dość potężnych) gałęzi obliczeniowych, tak że nie byłby w stanie stwierdzić, czy wszystkie własne gałęzie obliczeniowe odrzucały.

Jeśli trzymać się na dostarczaniu maszynę z mocniejszym wyrocznie do rozwiązywania problemów w , N P N P , i tak dalej, w końcu definiowanie klas z wielomianu hierarchii , które są uważane za wszystko różni się od siebie z pierwszy poziom wzwyż.$\mathsf{NP}$$\mathsf{NP}^{\mathsf{NP}}$

Tak więc nie, nie ma żadnej maszyny (deterministycznej lub innej), która mogłaby po prostu „zdecydować”, że problem jest efektywnie instancją TAK lub NIE, chyba że użyjemy wyroczni; Ale nawet z takim wyroczni, możemy skończyć z maszyny, która jest (prawdopodobnie) bardziej wydajne niż jednej NP lub CONP , a nie taki, który pokazuje, że są one równe.

Twoje rozumowanie sugeruje, że RE = coRE, ale jest to prawdopodobnie nieprawda. Możesz spróbować znaleźć na to dowód, a następnie sprawdzić, gdzie kończy się niepowodzenie.

Przypomnijmy, że RE jest klasą złożoności języków z wyliczaniem rekurencyjnym, które są językami postaci . Można również pomyśleć o tym w kategoriach non-deterministycznych: RE jest klasa języków postaci { x : ( x , w ) ∈ L '  dla niektórych  wag } , gdzie L ' jest rekurencyjne (obliczalne).$\{ x : P \text{ halts on input } x \}$$\{ x : (x,w) \in L' \text{ for some } w \}$$L'$

Oto dowód, że obie definicje są zgodne. Załóżmy, że pierwsze . Niech L ' = { ( x , wagowo ) : str  postojów na wejściowego  x  w  W  krokach } . Język L ' jest rekurencyjny, a L = { x : ( x , w ) ∈ L ′  dla niektórych  w } .$L = \{ x : p \text{ halts on input } x \}$$L' = \{ (x,w) : p \text{ halts on input } x \text{ in } w \text{ steps} \}$$L'$$L = \{ x : (x,w) \in L' \text{ for some } w \}$

Dla drugiego kierunku niech , gdzie L ' jest rekurencyjne, powiedzmy obliczone przez program P ( x , w ) . Konstruujemy nowy program Q ( x ), który wylicza wszystkie możliwe w i uruchamia P ( x , w ) na wszystkich w , w kolejności. Jeśli P ( x , $L = \{ x : (x,w) \in L' \text{ for some } w \}$$L'$$P(x,w)$$Q(x)$$w$$P(x,w)$$w$ kiedykolwiek akceptuje dla niektórych w , wtedy Q zatrzymuje się. Nietrudno sprawdzić, czy L = { x : Q  zatrzymuje się na wejściu  x } .$P(x,w)$$w$$Q$$L = \{ x : Q \text{ halts on input } x \}$

Dla Twojej wygody, oto zarys dowodu, że RE różni się od coRE. Język jest wyraźnie wyliczalny rekurencyjnie: program dla tego po prostu uruchamia P na x . Załóżmy, że było to program H , tak że H ( P , x ) zatrzymanie wtedy i tylko wtedy, gdy ( P , x ) ∉ l . Nowy program G definiujemy za pomocą G ( x ) $L = \{(P,x) : P \text{ halts on input x}\}$$P$$x$$H$$H(P,x)$$(P,x) \notin L$$G$ . Czy ( G , G ) ∈ L ? Jeśli tak, wtedy G zatrzymanie na G , tak, H postojów w ( G , G ) , tak, ( G , G ) ∉ L . Jeśli ( G , G ) ∉ L , to G nie zatrzymuje się na G , więc H nie zatrzymuje się na ( G , G $G(x)=H(x,x)$$(G,G) \in L$$G$$G$$H$$(G,G)$$(G,G) \notin L$$(G,G) \notin L$$G$$G$$H$$(G,G)$Tak . Ta sprzeczność pokazuje, że H. nie może istnieć.$(G,G) \in L$$H$

Teraz spróbuj uruchomić dowód w tym przypadku i zobacz, co poszło nie tak. Bardziej szczegółowo, spróbuj skonstruować program przy użyciu swojego przepisu i postępuj zgodnie z dowodem - w którymś momencie coś nie będzie w porządku.$H$

Oto wersja TL; DR; Opublikowałem również dłuższą odpowiedź na podobne pytanie.

Załóżmy, że mamy język że postanowił w czasie wielomianowym przez niedeterministycznych maszyna Turinga  M . Chodzi o to, że x ∈ IFF nie M  zawiera pewną przyjmującą ścieżkę na wejściowy  x . Ponieważ jednak M  jest niedeterministyczne, ścieżki mogą również odrzucać, gdy działa na  $A$$M$$x\in A$$M$$x$$M$$x$. Jeśli po prostu odwrócisz stan akceptacji i odrzucenia, przejdziesz z komputera, który ma kilka ścieżek akceptacji i niektórych odrzucających, na maszynę, która ma kilka ścieżek odrzucania i niektórych akceptacji. Innymi słowy, nadal ma ścieżki akceptacji, więc nadal akceptuje. Przerzucanie stanów akceptacji i odrzucenia maszyny niedeterministycznej na ogół nie powoduje zaakceptowania języka dopełniacza.

Ta asymetria definicji (akceptuj, jeśli którakolwiek ścieżka akceptuje; odrzucaj tylko wtedy, gdy wszystkie ścieżki odrzucają) sprawia, że problem NP vs co-NP jest trudny.

Zgadzam się, że twoja niedeterministyczna maszyna M może zdecydować, czy dany ciąg wejściowy znajduje się w B. Jednak „decyduje” nieco inaczej niż sposób, w jaki decyduje, czy dane wejście znajduje się w A. W tym drugim przypadku robi to poprzez ( niedeterministycznie) znalezienie stanu akceptującego. W pierwszym przypadku robi to, nie znajdując żadnych stanów akceptujących. Dlaczego ta różnica ma znaczenie? Zobaczmy:

Kiedy pytasz M „Czy łańcuch jest w języku A?”

M osiąga stan akceptacji. Można to udowodnić (patrz na przykład twierdzenie o książce Sipser 7.20), że istnieje maszyna deterministyczna, która sprawdza, czy łańcuch jest w A w czasie wielomianowym

Kiedy pytasz M „Czy łańcuch jest w języku B?”

M osiąga stany odrzucenia na wszystkich gałęziach swojego niedeterministycznego obliczenia. Jeśli pomyślisz o tym, jak działa powyższy dowód weryfikacyjny, zobaczysz, że nie można tego osiągnąć w tej sytuacji. Jest tak mniej więcej dlatego, że weryfikator wykorzystuje ścieżkę, którą M prowadzi przez swoją przestrzeń stanu jako „dowód”. W takim przypadku nie ma takiej ścieżki.

Wniosek:

Jeśli weźmiesz pod uwagę istnienie wielomianowego deterministycznego weryfikatora czasu dla języka jako definicji języka NP (co powinieneś), istnienie M nie dowodzi, że B jest w NP.