Twierdzenie Karpa-Liptona

Notacja zastosowana w tym artykule jest wyjaśniona na stronie hierarchia wielomianów .

W teorii złożoności twierdzenie Karpa -Liptona stwierdza, że ​​​​jeśli problem spełnialności Boole'a (SAT) można rozwiązać za pomocą obwodów Boole'a z wielomianową liczbą bramek logicznych, to

${\ Displaystyle \ Pi _ {2} = \ Sigma _ {2} \,}$ i dlatego ${\ Displaystyle \ operatorname {PH} = \ Sigma _ {2}. \,}$

To znaczy, jeśli założymy, że NP , klasa niedeterministycznych wielomianowych problemów czasowych, może być zawarta w niejednorodnej wielomianowej klasie złożoności czasowej P/poly , to założenie to implikuje załamanie hierarchii wielomianowej na jej drugim poziomie. Uważa się, że takie załamanie jest mało prawdopodobne, więc twierdzenie to jest ogólnie postrzegane przez teoretyków złożoności jako dowód na nieistnienie obwodów o rozmiarach wielomianowych dla SAT lub innych problemów NP-zupełnych . Dowód, że takie obwody nie istnieją, sugerowałby, że P ≠ NP . Ponieważ P/poly zawiera wszystkie problemy rozwiązywalne w losowym czasie wielomianowym ( twierdzenie Adlemana ), twierdzenie to jest również dowodem na to, że zastosowanie randomizacji nie prowadzi do algorytmów czasu wielomianowego dla problemów NP-zupełnych.

Twierdzenie Karpa-Liptona zostało nazwane na cześć $.$ M. Karpa i Richarda J. Liptona , którzy po raz pierwszy udowodnili (Ich oryginalny dowód upadł PH do , ale Michael Sipser go poprawił do ${\ Displaystyle \ Sigma _ {2}}$ .)

Warianty twierdzenia stwierdzają, że przy tym samym założeniu SP ^MA
₂ = AM i PH załamuje się do klasy złożoności . Możliwe są silniejsze wnioski, jeśli PSPACE lub inne klasy złożoności mają obwody o wielkości wielomianu; patrz P/poli . Jeśli zakłada się, że NP jest podzbiorem BPP (który jest podzbiorem P/poly), to hierarchia wielomianów zapada się do BPP . Jeśli zakłada się, że coNP jest podzbiorem NP/poly , to hierarchia wielomianów spada do trzeciego poziomu.

Intuicja

Załóżmy, że obwody SAT o rozmiarach wielomianowych nie tylko istnieją, ale także, że można je skonstruować za pomocą algorytmu czasu wielomianowego. Wtedy to przypuszczenie implikuje, że sam SAT można rozwiązać za pomocą algorytmu czasu wielomianowego, który konstruuje obwód, a następnie go stosuje. Oznacza to, że wydajnie konstruowalne obwody dla SAT doprowadziłyby do silniejszego załamania, P = NP.

Założenie twierdzenia Karpa-Liptona, że ​​takie obwody istnieją, jest słabsze. Ale nadal możliwe jest $,$ aby algorytm w klasie złożoności prawidłowy obwód dla SAT Klasa złożoności opisuje problemy postaci ${\ displaystyle \ Sigma _ {2}}$

${\ Displaystyle \ istnieje x \ forall y \; \ psi (x, y)}$

gdzie jest $obliczalnym$ predykatem w czasie wielomianowym. Moc egzystencjalna pierwszego kwantyfikatora w tym predykacie może być wykorzystana do odgadnięcia prawidłowego obwodu dla SAT, a uniwersalna moc drugiego kwantyfikatora może zostać wykorzystana do sprawdzenia, czy obwód jest poprawny. Gdy ten obwód zostanie odgadnięty i zweryfikowany, algorytm w klasie $może$ użyć go jako podprogramu do rozwiązywania innych

Samoredukowalność

Aby bardziej szczegółowo zrozumieć dowód Karpa-Liptona, rozważymy problem testowania, czy obwód c jest poprawnym obwodem do rozwiązywania instancji SAT o danym rozmiarze, i pokazujemy, że ten problem testowania obwodu należy do ${\ displaystyle \ Pi _{1}}$ . Oznacza to, że istnieje predykat V obliczalny w czasie wielomianowym, taki, że c jest poprawnym obwodem wtedy i tylko wtedy, gdy dla wszystkich wielomianowo ograniczonych z , V ( c , z ) jest prawdziwe.

Obwód c jest prawidłowym obwodem dla SAT, jeśli spełnia dwie właściwości:

• Dla każdej pary ( s , x ), gdzie s jest instancją SAT i x jest rozwiązaniem tej instancji, c ( s ) musi być prawdziwe
• Dla każdego przypadku s SAT, dla którego c ( s ) jest prawdziwe, s musi być rozwiązywalne.

Pierwsza z tych dwóch właściwości ma już postać problemów w klasie ${\ displaystyle \ Pi _ {1}}$ . Aby zweryfikować drugą właściwość, używamy samoredukowalności SAT.

₀ Samoredukowalność opisuje zjawisko polegające na tym, że jeśli możemy szybko sprawdzić, czy instancja SAT jest rozwiązywalna, prawie równie szybko możemy znaleźć jawne rozwiązanie tej instancji. Aby znaleźć rozwiązanie dla wystąpienia s , wybierz jedną ze zmiennych boolowskich x , które są wprowadzane do s , i utwórz dwa mniejsze przypadki s i s _{1 ,} gdzie s _i oznacza formułę utworzoną przez zastąpienie x stałą i . Po zbudowaniu tych dwóch mniejszych instancji zastosuj test rozwiązywalności do każdej z nich. Jeśli jeden z tych dwóch testów zwróci, że mniejsza instancja jest zadowalająca, kontynuuj rozwiązywanie tej instancji, aż do uzyskania kompletnego rozwiązania.

Aby użyć samoredukowalności do sprawdzenia drugiej właściwości prawidłowego obwodu dla SAT, przepisujemy go w następujący sposób:

• Dla każdego przypadku s SAT, dla którego c ( s ) jest prawdziwe, procedura samoredukcji opisana powyżej znajduje ważne rozwiązanie dla s .

W ten sposób możemy sprawdzić, $czy$ c jest prawidłowym obwodem do rozwiązywania

zobacz Losowa samoredukowalność, aby uzyskać więcej informacji

Dowód twierdzenia Karpa-Liptona

Twierdzenie Karpa – Liptona można przekształcić w wyniku formuł boolowskich z kwantyfikatorami ograniczonymi wielomianami. Problemy w opisują formuły tego typu o składni ${\ displaystyle \ Pi _ {2}}$

${\ Displaystyle \ phi = \ forall x \ istnieje y \; \ psi (x, y)}$

gdzie jest $wielomianowym$ . Twierdzenie Karpa-Liptona stwierdza, że ​​ten typ formuły można przekształcić w czasie wielomianowym w formułę równoważną, w której kwantyfikatory występują w odwrotnej kolejności; taka formuła należy do ${\ displaystyle \ Sigma _ {2}}$ . Zauważ, że podformuła

${\ Displaystyle s (x) = \ istnieje y \; \ psi (x, y)}$

jest instancją SAT. Oznacza to, że jeśli c jest prawidłowym obwodem dla SAT, to ta formuła podrzędna jest równoważna niekwantyfikowanemu wzorowi c ( s ( x )). Dlatego pełny wzór na jest równoważny (przy założeniu, że istnieje ważny obwód c ) do wzoru ${\ displaystyle \ phi}$

$\ forall (x, z) \; V (c, z) \ klin c (s (x) ))\,}$

gdzie V jest wzorem używanym do sprawdzenia, czy c naprawdę jest prawidłowym obwodem przy użyciu samoredukowalności, jak opisano powyżej. Ta równoważna formuła ma swoje kwantyfikatory w odwrotnej kolejności, zgodnie z potrzebami. Założenie Karpa-Liptona pozwala więc na transpozycję kolejności kwantyfikatorów egzystencjalnych i uniwersalnych we wzorach tego typu, pokazując, że ${\ Displaystyle \ Sigma _ {2} = \ Pi _ {2}.}$${\ Displaystyle PH = \ Sigma _ {2}.}$ której mają one pojedynczy kwantyfikator egzystencjalny, po którym następuje pojedynczy kwantyfikator uniwersalny, pokazujący, że

Kolejny dowód i S
^P ₂

Załóżmy ${\ Displaystyle {\ mathsf {NP}} \ subseteq {\ mathsf {P / poli}}}$ . Dlatego istnieje rodzina obwodów $,$ która rozwiązuje spełnialność na wejściu n . Wykorzystując samoredukowalność, istnieje rodzina obwodów $,$ która daje satysfakcjonujące przypisanie w prawdziwych

Załóżmy $,$ L jest _

${\ Displaystyle L = \ {z: \ dla wszystkich x. \ istnieje y. \ phi (x, y, z) \} \,}$

Od ${\ Displaystyle \ istnieje y. \ phi (x, y, z)}$ można uznać za instancję SAT (zgodnie z twierdzeniem Cooka-Levina ), istnieje obwód ${\ displaystyle D_ {n}}$ , w zależności od ${\ displaystyle n = | z|}$ , tak że formuła definiująca L jest równoważna

${\ Displaystyle \ forall x. \ phi (x, D_ {n} (x, z), z)}$

 

 

 

 

()

Ponadto obwód można odgadnąć za pomocą kwantyfikacji egzystencjalnej:

${\ Displaystyle \ istnieje D. \ forall x. \ phi (x, D (x, z), z)}$

 

 

 

 

()

Oczywiście ( 1 ) implikuje ( 2 ). Jeśli (1) jest fałszywe, to ${\ Displaystyle \ neg \ istnieje y. \ phi (x, y, z)}$ . $_$ przypadku D przypisania _

Dowód wykazał, że $\ Sigma _ {2}$$displaystyle$ w Π $\$ .

Co więcej, jeśli $wzór jest$ prawdziwy , to obwód D będzie działał przeciwko x Jeśli $fałszywa$ , to x uczynienie formuły (1) fałszywą będzie działać przeciwko dowolnemu obwodowi Właściwość ta oznacza silniejszy upadek, a mianowicie do złożoności SP ^⊆
_{2 (tj.} ${\ Displaystyle \ Pi _ {2} \ subseteq {\ mathsf {S}} _ {2} ^ {P} \ subseteq \ Sigma _ {2}})$ . Zauważył to Sengupta.

AM = MA

Modyfikacja powyższego dowodu daje wynik

${\ Displaystyle {\ mathsf {NP}} \ subseteq {\ mathsf {P / poli}} \ implikuje {\ mathsf {AM}} = {\ mathsf { MAMA}}}$

(patrz protokół Artura-Merlina ).

Załóżmy, że L jest w AM , tj.:

${\ Displaystyle z \ w L \ implikuje \ Pr \ nolimits _ {x} [\ istnieje y. \ phi (x, y, z)] \ geq {\ tfrac { 2}{3}}}$

${\ Displaystyle z \ notin L \ implikuje \ Pr \ nolimits _ {x} [\ istnieje y. \ phi (x, y, z)] \ równoważnik {\ tfrac {1} {3}}}$

i jak poprzednio przepisujemy ${\ Displaystyle \ istnieje y. \ phi (x, y, z)}$ przy użyciu obwodu , który wyprowadza satysfakcjonujące przypisanie, jeśli istnieje: re $\ displaystyle D_ {n}}$

${\ Displaystyle z \ w L \ implikuje \ Pr \ nolimits _ {x} [\ phi (x, D_ { n}(x,z),z)]\geq {\tfrac {2}{3}}}$

${\ Displaystyle z \ notin L \ implikuje \ Pr \ nolimits _ {x} [\ phi (x, D_ {n} (x, z), z)] \ równoważnik {\ tfrac {1} 3}}}$

Ponieważ można się domyślić: $\ displaystyle D_ {n}}$

${\ Displaystyle z \ w L \ implikuje \ istnieje D. \ Pr \ nolimits _ {x} [\ phi (x, D (x ,z),z)]\geq {\tfrac {2}{3}}}$

${\ Displaystyle z \ notin L \ implikuje \ dla wszystkich D. \ Pr \ nolimits _ {x} [\ phi (x, D (x, z), z)] \ równoważnik {\ tfrac {1}{3}}}$

co dowodzi, $że$ do mniejszej klasy MA .

Zastosowanie do dolnych granic obwodów – twierdzenie Kannana

Twierdzenie Kannana stwierdza, że ​​​​dla dowolnego ustalonego k $\ displaystyle$ w , który nie ma ROZMIARU (n ^k ) (Jest to inne stwierdzenie niż $L}$${\ Displaystyle \ Sigma _ {2} \ not \ subseteq {\ mathsf {P / poly}}}$ , który jest obecnie otwarty i stwierdza, że ​​istnieje jeden język, którego nie ma w ROZMIARZE (n ^k ) dla dowolnego k ). Jest to prosty obwód dolna granica .

Zarys dowodu:

L ${\ Displaystyle L \ in \ Sigma _ {4} - {\ mathsf {ROZMIAR}} (n ^ {k})}$ dowód wykorzystuje diagonalizację technika). Rozważ dwa przypadki:

• Jeśli ${\ Displaystyle {\ mathsf {SAT}} \ notin {\ mathsf {P / poli}}}$ to ${\ Displaystyle { \mathsf {SAT}}\notin {\mathsf {ROZMIAR}}(n^{k})}$ i twierdzenie zostało udowodnione.
• Jeśli ${\ Displaystyle {\ mathsf {SAT}} \ in {\ mathsf {P / poli}}}$ , to według twierdzenia Karpa-Liptona ${\ Displaystyle \ Sigma _ {4} = \ Sigma _ {2}}$ , a zatem $\ Displaystyle L \ w \ Sigma _ {2} - {\ mathsf {ROZMIAR}} (n ^{k})}$ .

Silniejsza wersja twierdzenia Karpa-Liptona wzmacnia twierdzenie Kannana do: dla dowolnego k istnieje język ${\ Displaystyle L \ w {\ mathsf {S}} _ { 2}^{P}-{\mathsf {ROZMIAR}}(n^{k})}$ .

Wiadomo również, że $nie$ jest zawarte w Dowód:

• P. ${\ Displaystyle {\ mathsf {PP}} \ nie \ subseteq {\ mathsf {P / poli}}}, a$ następnie ${\ Displaystyle { \mathsf {PP}}\not \subseteq {\mathsf {ROZMIAR}}(n^{k})}$ .
• W przeciwnym razie ${\ Displaystyle {\ mathsf {P ^ {\ # P}}} \ subseteq {\ mathsf {P / poli}}}$ . Od

${\ Displaystyle {\ mathsf {P ^ {\ # P}}} \ supseteq {\ mathsf {PP}} \ supseteq {\ mathsf {MA}}} (według$ właściwości MA )

${\ Displaystyle {\ mathsf {P ^ {\ # P}}} \ supseteq {\ mathsf {PH}} \ supseteq \ Sigma _ {2} \ supseteq {\ mathsf {MA}}}$ (z twierdzenia Tody i własności MA)

${\ Displaystyle {\ mathsf {P ^ {\ # P}}} = {\ mathsf {MA}}}$ (wynika z założenia przy użyciu protokołu interaktywnego na stałe, patrz P / poly )

ograniczenia są równościami i otrzymujemy ${\ Displaystyle {\ mathsf {PP}} = \ Sigma _ {2} \ nie \ subseteq {\ mathsf {ROZMIAR}} (n ^ {k})}$ przez twierdzenie Kannana .

•   Karp, RM ; Lipton, RJ (1980), „Niektóre połączenia między niejednorodnymi i jednolitymi klasami złożoności”, Proceedings of the XII Annual ACM Symposium on Theory of Computing , s. 302–309, doi : 10.1145/800141.804678 , S2CID 1458043 .

• Karp, RM ; Lipton, RJ (1982), „Maszyny Turinga, które przyjmują rady”, L'Enseignement Mathématique , 28 : 191–209, doi : 10,5169/seals-52237 .