Hierarchia wielomianowa - Polynomial hierarchy

W teorii złożoności obliczeniowej , wielomian hierarchia (czasami nazywany hierarchia wielomian-time ) jest hierarchia z klasami złożoności że uogólnienia klasy NP i współ-NP . Każda klasa w hierarchii jest zawarta w PSPACE . Hierarchię można zdefiniować za pomocą maszyn oracle lub naprzemiennych maszyn Turinga . Jest to ograniczony do zasobów odpowiednik hierarchii arytmetycznej i hierarchii analitycznej z logiki matematycznej . Związek klas w hierarchii oznaczono jako PH .

Klasy w hierarchii mają kompletne problemy (w odniesieniu do wielomianowych redukcji w czasie ), które pytają, czy kwantyfikowane formuły Boole'a są spełnione , dla formuł z ograniczeniami w kolejności kwantyfikatorów. Wiadomo, że równość między klasami na tym samym poziomie lub kolejnymi poziomami w hierarchii oznaczałaby „upadek” hierarchii do tego poziomu.

Definicje

Istnieje wiele równoważnych definicji klas hierarchii wielomianowej.

Definicja Oracle

Aby uzyskać wyrocznią definicję hierarchii wielomianowej, zdefiniuj

{\ Displaystyle \ Delta _ {0} ^ {\ mathsf {P}}: = \ Sigma _ {0} ^ {\ mathsf {P}}: = \ pi _ {0} ^ {\ mathsf {P}}: ={\mathsf {P}},}

gdzie P jest zbiorem problemów decyzyjnych rozwiązywalnych w czasie wielomianowym . Wtedy dla i ≥ 0 zdefiniuj

{\ Displaystyle \ Delta _ {i + 1} ^ {\ mathsf {P}}: = {\ mathsf {P}} ^ {\ Sigma _ {i} ^ {\ mathsf {P}}}}

{\ Displaystyle \ Sigma _ {i + 1} ^ {\ mathsf {P}}: = {\ mathsf {NP}} ^ {\ Sigma _ {i} ^ {\ mathsf {P}}}}

{\ Displaystyle \ Pi _ {i + 1} ^ {\ mathsf {P}}: = {\ mathsf {coNP}} ^ {\ Sigma _ {i} ^ {\ mathsf {P}}}}

gdzie jest zbiorem problemów decyzyjnych rozwiązywanych w czasie wielomianowym przez maszynę Turinga powiększoną o wyrocznię dla jakiegoś kompletnego problemu w klasie A; klasy i są zdefiniowane analogicznie. Na przykład , i jest klasą problemów rozwiązywalnych w czasie wielomianowym za pomocą wyroczni dla jakiegoś problemu NP-zupełnego. ${\ Displaystyle {\ mathsf {P}} ^ {\ RM {A}}}$ ${\ Displaystyle {\ mathsf {NP}} ^ {\ RM {A}}}$ ${\ Displaystyle {\ mathsf {coNP}} ^ {\ rm {A}}}$ ${\ Displaystyle \ Sigma _ {1} ^ {\ mathsf {P}} = {\ mathsf {NP}}, \ pi _ {1} ^ {\ mathsf {P}} = {\ mathsf {coNP}}}$ ${\ Displaystyle \ Delta _ {2} ^ {\ mathsf {P}} = {\ mathsf {P ^ {NP}}}}$

Ilościowa definicja formuł logicznych

Dla egzystencjalnej/uniwersalnej definicji hierarchii wielomianowej niech $L$ będzie językiem (tj. problemem decyzyjnym , podzbiorem {0,1} ^* ), niech $p$ będzie wielomianem i zdefiniujemy

{\ Displaystyle \ istnieje ^ {p} L: = \ lewo \ {x \ w \ {0, 1 \} ^ {*} \ \ lewo | \ \ lewo (\ istnieje w \ w \ {0,1 \} ^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\},}

gdzie jest pewne standardowe kodowanie pary ciągów binarnych x i w jako pojedynczy ciąg binarny. L reprezentuje zestaw uporządkowanych par ciągów, gdzie pierwszy ciąg x należy do , a drugi ciąg w jest „krótkim” ( ) świadkiem świadczącym, że x należy do . Innymi słowy, wtedy i tylko wtedy, gdy istnieje krótkie świadectwo wagowo takie, że . Podobnie, zdefiniuj ${\ Displaystyle \ langle x, w \ rangle \ w \ {0,1 \} ^ {*}}$ ${\ Displaystyle \ istnieje ^ {p} L}$ $|w|\leq p(|x|)$ ${\ Displaystyle \ istnieje ^ {p} L}$ ${\ Displaystyle x \ w \ istnieje ^ {p} L}$ ${\ Displaystyle \ langle x, w \ rangle \ w l}$

{\ Displaystyle \ forall ^ {p} L: = \ lewo \ {x \ w \ {0,1 \} ^ {*} \ \ lewo | \ \ lewo (\ dla wszystkich w \ w \ {0,1 \} ^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\}}

Należy pamiętać, że prawa De Morgana przytrzymanie: i gdzie L ^c jest dopełnieniem L . ${\ Displaystyle \ lewo (\ istnieje ^ {p} L \ po prawej) ^ {\ rm {c}} = \ dla wszystkich ^ {p} L ^ {\ rm {c}}}$ ${\ Displaystyle \ lewo (\ forall ^ {p} L \ po prawej) ^ {\ rm {c}} = \ istnieje ^ {p} L ^ {\ rm {c}}}$

Niech C będzie klasą języków. Rozszerz te operatory, aby działały na całych klasach języków zgodnie z definicją

{\ Displaystyle \ istnieje ^ {\ mathsf {P}} {\ mathcal {C}}: = \ lewo \ {\ istnieje ^ {p} L \ | \ p {\ tekst { jest wielomianem i}} L \ w {\mathcal {C}}\right\}}

{\ Displaystyle \ forall ^ {\ mathsf {P}} {\ mathcal {C}}: = \ lewo \ {\ forall ^ {p} L \ | \ p {\ tekst { jest wielomianem i}} L \ w {\mathcal {C}}\right\}}

Znowu obowiązują prawa De Morgana: i , gdzie . ${\mathsf {co}}\istnieje ^{\mathsf {P}}{\mathcal {C}}=\forall ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C }}$ ${\mathsf {co}}\forall ^{\mathsf {P}}{\mathcal {C}}=\istnieje ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C }}$ ${\ Displaystyle {\ mathsf {co}} {\ mathcal {C}} = \ lewo \ {L ^ {c} | L \ w {\ mathcal {C}} \ prawej \}}$

Klasy NP i co-NP można zdefiniować jako , i , gdzie P jest klasą wszystkich wykonalnych (wielomianowych) języków rozstrzygalnych. Hierarchię wielomianową można zdefiniować rekurencyjnie jako ${\ Displaystyle {\ mathsf {NP}} = \ istnieje ^ {\ mathsf {P}} {\ mathsf {P}}}$ ${\mathsf {coNP}}=\forall ^{\mathsf {P}}{\mathsf {P}}$

{\ Displaystyle \ Sigma _ {0} ^ {\ mathsf {P}}: = \ pi _ {0} ^ {\ mathsf {P}}: = {\ mathsf {P}}}

{\ Displaystyle \ Sigma _ {k + 1} ^ {\ mathsf {P}}: = \ istnieje ^ {\ mathsf {P}} \ Pi _ {k} ^ {\ mathsf {P}}}

{\ Displaystyle \ Pi _ {k + 1} ^ {\ mathsf {P}}: = \ forall ^ {\ mathsf {P}} \ Sigma _ {k} ^ {\ mathsf {P}}}

Zauważ, że i . ${\ Displaystyle {\ mathsf {NP}} = \ Sigma _ {1} ^ {\ mathsf {P}}}$ ${\ Displaystyle {\ mathsf {coNP}} = \ pi _ {1} ^ {\ mathsf {P}}}$

Definicja ta odzwierciedla ścisły związek między hierarchią wielomianową a hierarchią arytmetyczną , gdzie R i RE odgrywają role analogiczne do P i NP , odpowiednio. Analityczna hierarchia jest także zdefiniowana w podobny sposób, aby dać hierarchię podzbiorów liczb rzeczywistych.

Naprzemienna definicja maszyn Turinga

Maszyna Turinga przemiennego jest niedeterministyczne maszyny Turinga z państwa niebędącego końcowych podzielony na stany egzystencjalne i uniwersalnych. Ostatecznie akceptuje ze swojej obecnej konfiguracji, jeśli: jest w stanie egzystencjalnym i może przejść do jakiejś ostatecznie akceptującej konfiguracji; lub jest w stanie uniwersalnym i każde przejście jest w jakiejś ostatecznie akceptującej konfiguracji; lub jest w stanie akceptacji.

Definiujemy jako klasę języków akceptowaną przez przemienną maszynę Turinga w czasie wielomianowym, tak że stan początkowy jest stanem egzystencjalnym, a każda ścieżka, którą maszyna może przejść co najwyżej k – 1 razy między stanami egzystencjalnymi i uniwersalnymi. Definiujemy podobnie, z tą różnicą, że stan początkowy jest stanem uniwersalnym. ${\ Displaystyle \ Sigma _ {k} ^ {\ mathsf {P}}}$ ${\ Displaystyle \ Pi _ {k} ^ {\ mathsf {P}}}$

Jeśli pominiemy wymóg co najwyżej k – 1 zamian między stanami egzystencjalnymi i uniwersalnymi, tak że wymagamy tylko, aby nasza przemienna maszyna Turinga działała w czasie wielomianowym, to mamy definicję klasy AP , która jest równa PSPACE .

Relacje między klasami w hierarchii wielomianowej

Diagram przemienny równoważny wielomianowej hierarchii czasu. Strzałki oznaczają włączenie.

Związek wszystkich klas w hierarchii wielomianowej to klasa złożoności PH .

Definicje implikują relacje:

{\ Displaystyle \ Sigma _ {i} ^ {\ mathsf {P}} \ subseteq \ Delta _ {i + 1} ^ {\ mathsf {P}} \ subseteq \ Sigma _ {i + 1} ^ {\ mathsf { P}}}

{\ Displaystyle \ Pi _ {i} ^ {\ mathsf {P}} \ subseteq \ Delta _ {i + 1} ^ {\ mathsf {P}} \ podseteq \ Pi _ {i + 1} ^ {\ mathsf { P}}}

{\ Displaystyle \ Sigma _ {i} ^ {\ mathsf {P}} = {\ mathsf {co}} \ pi _ {i} ^ {\ mathsf {P}}}

W przeciwieństwie do hierarchii arytmetycznych i analitycznych, o których wtrąceniach wiadomo, że są właściwe, kwestią otwartą pozostaje, czy którykolwiek z tych wtrąceń jest właściwy, chociaż powszechnie uważa się, że wszystkie są prawidłowe. Jeśli istnieje , lub jeśli istnieje , hierarchia upada do poziomu k : dla wszystkich , . W szczególności mamy następujące implikacje dotyczące nierozwiązanych problemów: ${\ Displaystyle \ Sigma _ {k} ^ {\ mathsf {P}} = \ Sigma _ {k + 1} ^ {\ mathsf {P}}}$ ${\ Displaystyle \ Sigma _ {k} ^ {\ mathsf {P}} = \ Pi _ {k} ^ {\ mathsf {P}}}$ $i>k$ ${\ Displaystyle \ Sigma _ {i} ^ {\ mathsf {P}} = \ Sigma _ {k} ^ {\ mathsf {P}}}$

P = NP wtedy i tylko wtedy, gdy P = PH .
Jeśli NP = współ-NP to NP = PH . ( współ-NP to .) ${\ Displaystyle \ Pi _ {1} ^ {\ mathsf {P}}}$

Przypadek, w którym NP = PH jest również określany jako zapadnięcie się PH do drugiego poziomu . Przypadek P = NP odpowiada zawaleniu się PH do P .

Nierozwiązany problem w informatyce :

${\ Displaystyle {\ mathsf {P}} {\ przesłonięty {?} {=}} {\ mathsf {NP}}}$

(więcej nierozwiązanych problemów w informatyce)

Kwestia upadku do pierwszego poziomu jest ogólnie uważana za niezwykle trudną. Większość badaczy nie wierzy w załamanie, nawet do drugiego poziomu.

Relacje z innymi klasami

Nierozwiązany problem w informatyce :

${\ Displaystyle {\ mathsf {PH}}{\ przesłonięty {?}{=}}{\ mathsf {PSPACE}}}$

(więcej nierozwiązanych problemów w informatyce)

Hierarchia wielomianowa jest odpowiednikiem (o znacznie mniejszej złożoności) hierarchii wykładniczej i hierarchii arytmetycznej .

Wiadomo, że PH jest zawarte w PSPACE , ale nie wiadomo, czy te dwie klasy są sobie równe. Jednym z użytecznych przeformułowań tego problemu jest to, że PH = PSPACE wtedy i tylko wtedy, gdy logika drugiego rzędu nad skończonymi strukturami nie zyskuje żadnej dodatkowej mocy z dodania przechodniego operatora domknięcia .

Jeśli hierarchia wielomianowa ma jakieś kompletne problemy , to ma tylko skończenie wiele odrębnych poziomów. Ponieważ istnieją problemy z PSPACE-zupełnym , wiemy, że jeśli PSPACE = PH, to hierarchia wielomianów musi się załamać, ponieważ problem PSPACE-zupełny byłby problemem -zupełnym dla niektórych k . ${\ Displaystyle \ Sigma _ {k} ^ {\ mathsf {P}}}$

Każda klasa w hierarchii wielomianowej zawiera -zadania zupełne (zadania zupełne przy redukcji wielomianowej wiele-jednej). Co więcej, każda klasa w hierarchii wielomianu jest zamknięta pod -redukcjami : co oznacza, że dla klasy C w hierarchii i języku , jeśli , to również. Te dwa fakty razem wskazują, że jeśli jest kompletnym problemem dla , to , i . Na przykład . Innymi słowy, jeśli język jest zdefiniowany na podstawie jakiejś wyroczni w C , to możemy założyć, że jest zdefiniowany w oparciu o kompletny problem dla C . Problemy zupełne pełnią zatem rolę „przedstawicieli” klasy, dla której są zupełne. ${\ Displaystyle \ leq _ {\ rm {m}} ^ {\ mathsf {P}}}$ ${\ Displaystyle \ leq _ {\ rm {m}} ^ {\ mathsf {P}}}$ ${\ Displaystyle L \ w {\ matematyczny {C}}}$ ${\ Displaystyle A \ leq _ {\ rm {m}} ^ {\ mathsf {P}} L}$ ${\ Displaystyle A \ w {\ matematyczny {C}}}$ ${\ Displaystyle K_ {i}}$ ${\ Displaystyle \ Sigma _ {i} ^ {\ mathsf {P}}}$ ${\ Displaystyle \ Sigma _ {i + 1} ^ {\ mathsf {P}} = {\ mathsf {NP}} ^ {K_ {i}}}$ ${\ Displaystyle \ Pi _ {i + 1} ^ {\ mathsf {P}} = {\ mathsf {coNP}} ^ {K_ {i}}}$ ${\ Displaystyle \ Sigma _ {2} ^ {\ mathsf {P}} = {\ mathsf {NP}} ^ {\ mathsf {SAT}}}$

Twierdzenie Sipsera-Lautemanna stwierdza, że klasa BPP jest zawarta na drugim poziomie hierarchii wielomianowej.

Twierdzenie Kannana mówi, że dla dowolnego k , nie jest zawarte w ROZMIAR (n ^k ). ${\ Displaystyle \ Sigma _ {2}}$

Twierdzenie Tody mówi, że hierarchia wielomianowa jest zawarta w P ^#P .

Problemy

Przykładem naturalnego problemu jest minimalizacja obwodu : mając liczbę k i obwód A obliczający funkcję logiczną f , określ, czy istnieje obwód z co najwyżej k bramkami, który oblicza tę samą funkcję f . Niech C będzie zbiorem wszystkich obwodów logicznych. Język ${\ Displaystyle \ Sigma _ {2} ^ {\ mathsf {P}}}$
${\ Displaystyle L = \ lewo \ {\ langle A, k, B, x \ rangle \ w {\ mathcal {C}} \ razy \ mathbb {N} \ razy {\ mathcal {C}} \ razy \ {0 ,1\}^{*}\left|B{\text{ ma najwyżej }}k{\text{ bramek i }}A(x)=B(x)\right.\right\}}$

jest rozstrzygalna w czasie wielomianowym. Język

${\ Displaystyle {\ mathit {CM}} = \ lewo \ {\ langle A, k \ rangle \ w {\ mathcal {C}} \ razy \ mathbb {N} \ lewo | {\ zacząć {macierz} {\ tekst {istnieje obwód }}B{\text{ z co najwyżej }}k{\text{ bramkami }}\\{\text{ taki, że }}A{\text{ i }}B{\text{ obliczają ta sama funkcja}}\end{matrix}}\right.\right\}}$
jest językiem minimalizacji obwodów. ponieważ $L$ jest rozstrzygalne w czasie wielomianowym i ponieważ, dane , wtedy i tylko wtedy, gdy istnieje obwód $B$ taki, że dla wszystkich wejść $x$ , . ${\ Displaystyle {\ mathit {CM}} \ w \ Sigma _ {2} ^ {\ mathsf {P}} (= \ istnieje ^ {\ mathsf {P}} \ forall ^ {\ mathsf {P}} {\ matematyka {P}})}$ ${\ Displaystyle \ langle A, k \ rangle }$ ${\ Displaystyle \ langle A, k \ rangle \ w {\ mathit {CM}}}$ ${\ Displaystyle \ langle A, k, B, x \ rangle \ w L}$
Kompletnym problemem dla jest spełnialność dla kwantyfikowanych formuł logicznych z k – 1 alternatywami kwantyfikatorów (w skrócie QBF _k lub QSAT _k ). To jest wersja problemu spełnialności logicznej dla . W tym zadaniu otrzymujemy wzór logiczny f ze zmiennymi podzielonymi na k zbiorów X ₁ , ..., X _k . Musimy ustalić, czy to prawda, że ${\ Displaystyle \ Sigma _ {k} ^ {\ mathsf {P}}}$ ${\ Displaystyle \ Sigma _ {k} ^ {\ mathsf {P}}}$
$\istnieje X_{1}\forall X_{2}\istnieje X_{3}\ldots f$
To znaczy, czy istnieje przypisanie wartości do zmiennych w X _{1 w} taki sposób, że dla wszystkich przypisań wartości w X ₂ istnieje przypisanie wartości do zmiennych w X ₃ , ... f jest prawdziwe? Powyższy wariant jest kompletny dla . Wariant, w którym pierwszy kwantyfikator to „dla wszystkich”, drugi to „istnieje” itd., jest kompletny dla . Każdy język jest podzbiorem problemu uzyskanego przez usunięcie ograniczenia alternatyw k – 1, PSPACE -complete problem TQBF . ${\ Displaystyle \ Sigma _ {k} ^ {\ mathsf {P}}}$ ${\ Displaystyle \ Pi _ {k} ^ {\ mathsf {P}}}$
Listę problemów w stylu Gareya/Johnsona, o których wiadomo, że są kompletne dla drugiego i wyższego poziomu hierarchii wielomianowej, można znaleźć w tym Kompendium .

Zobacz też

Bibliografia

Ogólne odniesienia

Arora, Sanjeev; Barak, Boaz (2009). Teoria złożoności: nowoczesne podejście . Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 978-0-521-42426-4. rozdział 1.4, „Maszyny jako struny i uniwersalna maszyna Turinga” oraz 1.7, „Dowód twierdzenia 1.9”
AR Meyera i LJ Stockmeyera . Problem równoważności dla wyrażeń regularnych z kwadratem wymaga przestrzeni wykładniczej. W Proceedings of the 13th IEEE Symposium on Switching and Automata Theory , s. 125–129, 1972. Artykuł wprowadzający hierarchię wielomianową.
LJ Stockmeyera . Hierarchia wielomianowa . Informatyka teoretyczna , vol.3, s. 1-22, 1976.
C. Papadimitriou . Złożoność obliczeniowa. Addison-Wesley, 1994. Rozdział 17. Hierarchia wielomianowa , s. 409-438.
Michael R. Garey i David S. Johnson (1979). Komputery i nierozwiązywalność: przewodnik po teorii NP-zupełności . WH Freemana. Numer ISBN 0-7167-1045-5. Sekcja 7.2: Hierarchia wielomianów, s. 161-167.

Languages

In other projects