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 , 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 ) 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 .
źródło
Odpowiedzi:
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żkaM 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.
źródło
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.N.U O ( n l o g(n)) nlog(n) M M
źródło
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.=? =?
źródło