Wada mojego NP = dowód CoNP?

12

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?

prostak
źródło
2
Jak szczegółowo wyjaśniają poniższe odpowiedzi, nie używasz poprawnie pojęcia „decydujący”. Problemy w CoNP nie wynikają z „odwróconego decydenta NP”. W problemach NP istnieje ważna asymetria między przyjęciem danych wejściowych („istnieją wybory niedeterministyczne, które prowadzą do ich zaakceptowania”) a ich odrzuceniem („wszystkie wybory niedeterministyczne prowadzą do odrzucenia”). Twój argument zakłada, że ​​odrzucenie ciągu znaków przez NP oznacza („istnieją niezdecydowane wybory, które prowadzą do odrzucenia”), i to jest wada. Innymi słowy, pomieszałeś swoje kwantyfikatory.
Andrej Bauer,
1
Odpowiedzi na to pytanie mogą okazać się pouczające.
Raphael
@Raphael O dziwo, to pytanie w ogóle nie wspomina o co-NP! (Chociaż zgadzam się, że jest to przydatna lektura dla kogoś, kto nie ma pewności co do tego rodzaju rzeczy).
David Richerby
@DavidRicherby Ponieważ odpowiedź brzmi „użyj definicji NP zamiast błędnej intuicji”, mam taką nadzieję!
Raphael
1
Ogólna zasada: konstrukcja „odwracania stanów końcowych” działa tylko w przypadku modeli deterministycznych. Dowiedz się, dlaczego NFA nie rozumie dlaczego. Zobacz także tutaj i tutaj .
Raphael

Odpowiedzi:

16

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 ).doo-N.P.miXP.doo-N.P.P.S.P.ZAdomi

  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 wM.w

Shaull
źródło
Nie jestem pewien, dlaczego to ma znaczenie. Moja definicja decydującego jest taka, że ​​akceptuję, jeśli dane wejściowe są w L, i odrzucam, jeśli dane wejściowe nie są w L. Ten decydujący może być deterministyczny lub niedeterministyczny. Mówię jednak, że L jest w NP i dlatego jeśli używam niedeterministycznej TM, zajmę czas wielomianowy. Mogę też wiedzieć, dlaczego odwrócenie bitu niekoniecznie uzupełnia język. Według mojej wiedzy CoNP = {L | nie L \ w NP}. Dlatego jeśli odwrócę bit, powinienem uzyskać odpowiedź?
Niech . Rozważ niedeterministyczną TM, która działa w następujący sposób - w jednym uruchomieniu zawsze wyświetla „odrzuć”. W innych seriach rozpoznaje L w czasie wielomianowym (możliwe, ponieważ L N P ). Zastanów się, co się stanie, jeśli odwrócisz bit - odrzucający przebieg staje się akceptowalny dla każdego wejścia, więc uzupełniona maszyna rozpoznaje Σ - co nie jest dopełnieniem, chyba że L = . Sugeruję dokładne przejrzenie definicji niedeterminizmu, aby w pełni to zrozumieć. L.N.P.L.L.N.P.ΣL.=
Shaull,
Nie chodzi mi o to, że zmieniam fragment każdej ścieżki obliczeniowej. Mam na myśli to, że jeśli moja TM akceptuje, oznacza to, że istnieje ścieżka obliczeniowa, która osiąga stan akceptacji. Oznacza to, że L jest w NP, co oznacza, że ​​dopełniacz jest w coNP. Jeśli moja TM odrzuca, oznacza to, że odrzuca każdą ścieżkę obliczeniową. Oznacza to, że dopełniacz jest w NP, co oznacza, że ​​L jest w CoNP.
4
@simpleton: Wiesz, że NTM nie ma dostępu do wszystkich ścieżek jednocześnie, tylko jedna ścieżka? Myślicie jak ktoś, kto deterministycznie analizuje zachowanie NTM z zewnątrz.
frafl
7
Myślę, że PO może odnieść korzyść z dokładniejszego przyjrzenia się definicji NP.
MCH
15

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, żeV.:{0,1}n×{0,1}poly(n){0,1}

  • dla każdej instancji TAK , istnieje certyfikat p { 0 , 1 } p o l y ( n ) taki, że V ( x , p ) = 1 ; ix{0,1}np{0,1}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{0,1}nV.(x,p)=0p{0,1}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 NPCONP , 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.Δ2)P.P.N.P.P.N.P.

  • 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Σ2)P.N.P.N.P.P.N.P.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ż.N.P.N.P.N.P.

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.

Niel de Beaudrap
źródło
Cześć, dziękuję wam i Shauli za komentarze. Czy mówisz, że NTM może rozpoznać język NP w czasie policy, ale nie może zdecydować o języku NP w czasie policy? Myślę, że właśnie to zakładam, gdy mówię, że mam decydujący problem z NP.
simpleton
2
Och, chyba rozumiem, co masz na myśli. Czy mówisz, że używam redukcji wyroczni, a to faktycznie pokazuje, że problem dotyczy (co jest prawdą, ponieważ N P P N P i C o N P P N P )? Redukcja wyroczni pokazuje, że UNSAT jest trudny do NP, ale wciąż muszę pokazać, że U N S A T N P , i nie mogę tego pokazać? P.N.P.N.P.P.N.P.dooN.P.P.N.P.UN.S.ZAT.N.P.
simpleton
5
Twardość NP jest zdefiniowana z redukcjami wielokrotnymi, a nie redukcjami wyroczni.
Yuval Filmus
6

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. zatrzymuje się na wejściu x}{x:(x,w)L. dla niektórych 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 zatrzymuje się na wejściu x}L.={(x,w):p zatrzymuje się na wejściu x w w kroki}L.L.={x:(x,w)L. dla niektórych 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 , wL.={x:(x,w)L. dla niektórych w}L.P.(x,w)Q(x)wP.(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)wQL.={x:Q zatrzymuje się na wejściu 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. zatrzymuje się na wejściu x}P.xH.H.(P.,x)(P.,x)L.sol . 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 )sol(x)=H.(x,x)(sol,sol)L.solsolH.(sol,sol)(sol,sol)L.(sol,sol)L.solsolH.(sol,sol)Tak . Ta sprzeczność pokazuje, że H. nie może istnieć.(sol,sol)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.

Yuval Filmus
źródło
2

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  xZAM.xZAM.xM.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.

David Richerby
źródło
-2

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.

Alex
źródło
1
M.bbM.