Dlaczego nie możemy skutecznie przerzucić odpowiedzi NDTM?

Przeczytałem kilka razy, że nie można skutecznie odwrócić odpowiedzi NDTM. Nie rozumiem jednak dlaczego. Na przykład, ze względu na NDTM $M$ , która działa w , w tym tekstu (punkt 3.3), stwierdzono, że nie jest jasne, w jaki inny NDTM można określić w czas Jak Flip mówiąc”.T O ( n 100 ) $O(n)$$T$$O(n^{100})$$M$

Mój problem jest następujący: Wyjście NDTM i tam istnieje sekwencja niedeterministycznych wyborów, które prowadzą do stanu akceptacji. Ponadto istnieje uniwersalna jednostka NDTM która może symulować każdy NDTM przy niewielkim (logarytmicznym) narzutu. Dlaczego więc nie możemy zbudować T w następujący sposób: Po pierwsze, symuluj M za pomocą uniwersalnego NDTM, który powinien być możliwy w czasie . Następnie wyślij 1 - odpowiedź M. Oznaczałoby to, że możemy przerzucić odpowiedź dowolnego liniowego NDTM w czasie .$1$$NU$$O(n\log n)$$O(n\log n)$

Niedeterministyczna maszyna Turinga akceptuje, jeśli akceptuje co najmniej jedna ścieżka; odrzuca tylko wtedy, gdy wszystkie ścieżki odrzucą. Ta asymetria utrudnia „odwracanie odpowiedzi”.

Załóżmy na przykład, że masz niedeterministyczną maszynę Turinga  która ma dwie ścieżki wejściowe  : jedna akceptuje, a druga odrzuca.  ma co najmniej jedną ścieżkę akceptacji dla  , więc akceptuje. Załóżmy, że chcemy stworzyć maszynę, która akceptuje dokładnie dane wejściowe, które  odrzuca. Oczywistą pierwszą próbą jest przyjęcie  i odrzucenie stanów akceptujących, a stanów odrzucających.  ma jedną ścieżkę akceptującą dla  i jedną ścieżkę odrzucającą; ta nowa maszyna  ma jedną ścieżkę odrzucającą i jedną ścieżkę akceptującą. Tak więc nadal akceptuje  , który miał odrzucić!$M$$w$$M$$w$$M$$M$$M$$w$$M'$$w$

Niedeterministyczna maszyna nie może jednocześnie patrzeć na wszystkie swoje ścieżki i podejmować działań w oparciu o to, co robią wszystkie te ścieżki. Jeśli chcesz, możesz to potraktować jako formę paralelizmu, w którym wątki nie mogą się ze sobą komunikować. Po zakończeniu wszystkich wątków program musi zadać sobie następujące pytanie: „Czy przynajmniej jeden z moich wątków zaakceptował?” Jeśli odpowiedź brzmi „tak”, jest prawnie zobowiązany do przyjęcia; jeżeli odpowiedź jest przecząca, jest prawnie zobowiązany do odrzucenia. Nie może zrobić nic innego.

Kiedy symulujesz niedeterministyczną maszynę  za pomocą innej, , każda ścieżka  symuluje jedną ścieżkę  i widzi tylko tę ścieżkę. Nie może powiedzieć: „Jeśli wszystkie inne ścieżki zostaną odrzucone, zaakceptuję”, ponieważ nie widzi innych ścieżek; widzi tylko siebie. Mogłoby więc powiedzieć tylko: „Jeśli ścieżka, którą symulowałem, zostanie zaakceptowana, odrzucę” lub „Jeśli ścieżka, którą symuluję, zostanie zaakceptowana, też ją zaakceptuję”. Następnie, pod koniec obliczeń, maszyna musi powiedzieć: „Jeśli którakolwiek z moich ścieżek zostanie zaakceptowana, ja też ją zaakceptuję”, co prowadzi do problemu, który opisałem powyżej. Aby odwrócić zachowanie , każda ścieżka$M$$M'$$M'$$M$$M$$M'$musi powiedzieć: „Jeśli ścieżka, którą zasymulowałem, została zaakceptowana, odrzucam; w przeciwnym razie akceptuję”, a na końcu obliczeń maszyna musi powiedzieć: „Jeśli wszystkie moje ścieżki są akceptowane, akceptuję; w przeciwnym razie odrzucam . ” To dlatego, że jeśli wszystkie ścieżki symulatorze za przyjęte, że wszystkie środki z ścieżek jest odrzucony, więc odrzucony, więc potrzeby symulatora do zaakceptowania. Ale symulator nie jest prawidłową niedeterministyczną maszyną Turinga, ponieważ nie korzysta z prawnie obowiązującego kryterium akceptacji. Nie może tego zrobić.$M$$M$

Jedynym sposobem, w jaki możemy dowiedzieć się, czy niedeterministyczna maszyna odrzuca dane wejściowe, jest wypróbowanie każdej możliwej ścieżki i sprawdzenie, czy wszystkie one odrzucają. W końcu, jeśli choć jeden z nich zostanie zaakceptowany, maszyna zaakceptuje dane wejściowe. Ale wypróbowanie każdej możliwej ścieżki jest wykładniczo wolniejsze niż wypróbowanie tylko jednej.

Problem polega na tym, że NDTM są z natury niesymetryczne: czas oznacza, że ​​mają kroki O ( n ), aby odgadnąć ścieżkę akceptacji, jeśli istnieje, i odrzuci inaczej (jeśli nie istnieje ścieżka akceptacji).$O(n)$$O(n)$

Problem polega na tym, że jeśli twoja maszyna jest naprawdę w O ( n l o g ( n ) ) , oznacza to, że zgaduje w n l o g ( n ) kroków świadka, że M odrzuca dane wejściowe. Może to nie być możliwe, ponieważ nie ma świadków odrzucenia M , tylko świadków przyjęcia. Odrzucenie to brak świadka, więc nie jest łatwo udowodnić odrzucenie w krótkim czasie.$NU$$O(n log( n))$$n log (n)$$M$$M$

właściwie technicznie pytasz P pytanie coNP ( ? = NP), które jest otwarte. jest powszechnie przypuszczane, ale nie udowodniono, że nie są one równe. pozostałe odpowiedzi są intuicyjnymi szkicami / dowodami poszlakowymi, dlaczego nie są one równe.$\stackrel{?}{=}$$\stackrel{?}{=}$