Ierarhia polinomială
În teoria complexității , ierarhia polinomială este o ierarhie a claselor de complexitate care extinde noțiunea de clase P , NP , co-NP . Clasa PH este uniunea tuturor claselor ierarhiei polinomiale.
Definiții
Există mai multe definiții echivalente ale claselor ierarhiei polinomiale.
Ca alternanță de cuantificatori
Ierarhia poate fi definită folosind cuantificatorii universali ( ) și existențiali ( ). În primul rând, pentru orice polinom și orice limbaj , definim
∀{\ displaystyle \ forall}∃{\ displaystyle \ există} p{\ displaystyle p}L{\ displaystyle L}
∃pL: ={X∈{0,1}∗ | (∃w∈{0,1}≤p(|X|))⟨X,w⟩∈L}{\ displaystyle \ există ^ {p} L: = \ left \ {x \ in \ {0,1 \} ^ {*} \ \ left | \ \ left (\ există w \ in \ {0,1 \} ^ {\ leq p (| x |)} \ right) \ langle x, w \ rangle \ in L \ right. \ right \}},
adică setul conține exact setul de cuvinte pentru care există un cuvânt de dimensiune polinomială în lungimea lui x astfel încât cuvântul să fie în . Intuitiv, cuvântul joacă rolul unui certificat pentru , certificat relativ mic în comparație cu . La fel definim
∃pL{\ displaystyle \ există ^ {p} L}X{\ displaystyle x}w{\ displaystyle w}⟨X,w⟩{\ displaystyle \ langle x, w \ rangle}L{\ displaystyle L}w{\ displaystyle w}X{\ displaystyle x}X{\ displaystyle x}
∀pL: ={X∈{0,1}∗ | (∀w∈{0,1}≤p(|X|))⟨X,w⟩∈L}{\ displaystyle \ forall ^ {p} L: = \ left \ {x \ in \ {0,1 \} ^ {*} \ \ left | \ \ left (\ forall w \ in \ {0,1 \} ^ {\ leq p (| x |)} \ right) \ langle x, w \ rangle \ in L \ right. \ right \}}.
Extindem aceste definiții la clasele de limbă VS{\ displaystyle {\ mathcal {C}}}
∃PVS: ={∃pL | p este un polinom și L∈VS}{\ displaystyle \ există ^ {\ rm {P}} {\ mathcal {C}}: = \ left \ {\ există ^ {p} L \ | \ p {\ mbox {este un polinom și}} L \ in {\ mathcal {C}} \ right \}}
∀PVS: ={∀pL | p este un polinom și L∈VS}{\ displaystyle \ forall ^ {\ rm {P}} {\ mathcal {C}}: = \ left \ {\ forall ^ {p} L \ | \ p {\ mbox {este un polinom și}} L \ in {\ mathcal {C}} \ right \}}
Acum, putem defini clasele ierarhiei polinomiale prin inducție după cum urmează:
Σ0P: =Π0P: =P{\ displaystyle \ Sigma _ {0} ^ {\ rm {P}}: = \ Pi _ {0} ^ {\ rm {P}}: = {\ rm {P}}}
Σk+1P: =∃PΠkP{\ displaystyle \ Sigma _ {k + 1} ^ {\ rm {P}}: = \ există ^ {\ rm {P}} \ Pi _ {k} ^ {\ rm {P}}}
Πk+1P: =∀PΣkP{\ displaystyle \ Pi _ {k + 1} ^ {\ rm {P}}: = \ forall ^ {\ rm {P}} \ Sigma _ {k} ^ {\ rm {P}}}
PH=⋃k∈NUΣkP{\ displaystyle {\ rm {PH}} = {\ underset {k \ in \ mathbb {N}} {\ bigcup}} \ Sigma _ {k} ^ {\ rm {P}}}
În special, și .
NUP=Σ1P{\ displaystyle {\ rm {NP}} = \ Sigma _ {1} ^ {\ rm {P}}}vs.oNUP=Π1P{\ displaystyle {\ rm {coNP}} = \ Pi _ {1} ^ {\ rm {P}}}
Cu mașini oraculare
Ierarhia polinomială poate fi definită și cu ajutorul mașinii Turing cu oracle . denotă clasa de probleme care pot fi rezolvate de mașini de complexitate crescute de un oracol de complexitate .
LAB{\ displaystyle A ^ {B}}LA{\ displaystyle A}B{\ displaystyle B}
Noi pozăm
Δ0P=Σ0P=Π0P=P{\ displaystyle \ Delta _ {0} ^ {P} = \ Sigma _ {0} ^ {P} = \ Pi _ {0} ^ {P} = {\ mbox {P}}}Apoi pentru toate i ≥ 0:
Δeu+1P: =PΣeuP{\ displaystyle \ Delta _ {i + 1} ^ {P}: = {\ mbox {P}} ^ {\ Sigma _ {i} ^ {P}}}
Σeu+1P: =NPΣeuP{\ displaystyle \ Sigma _ {i + 1} ^ {P}: = {\ mbox {NP}} ^ {\ Sigma _ {i} ^ {P}}}
Πeu+1P: =co-NPΣeuP{\ displaystyle \ Pi _ {i + 1} ^ {P}: = {\ mbox {co-NP}} ^ {\ Sigma _ {i} ^ {P}}}
Cu mașini alternative
Ierarhia polinomială poate fi definită folosind mașini Turing alternative . este clasa de limbaje decisă de o mașină Turing alternativă în timp polinomial, în care orice execuție este compusă din i secvențe de configurații de același tip (existențiale sau universale), prima secvență conținând doar configurații existențiale. Definiția lui este similară, dar configurațiile din prima suită sunt universale.
ΣeuP{\ displaystyle \ Sigma _ {i} ^ {P}}ΠeuP{\ displaystyle \ Pi _ {i} ^ {P}}
Exemple de probleme
Dacă o formulă a logicii propoziționale este minimă, adică dacă nu există formule echivalente mai scurte, este o problemă algoritmică în .
Σ2P{\ displaystyle \ Sigma _ {2} ^ {P}}
Proprietăți
Întrebare despre prăbușire
O altă proprietate importantă, internă ierarhiei polinomiale, este:, ceea ce înseamnă că dacă la un nivel două clase sunt egale, atunci toate clasele „de mai sus” sunt egale. Vorbim apoi de „prăbușirea ierarhiei polinomiale la nivel ”.
∀eu,ΣeuP=ΠeuP⇒ΣeuP=PH{\ displaystyle \ forall i, \ Sigma _ {i} ^ {P} = \ Pi _ {i} ^ {P} \ Rightarrow \ Sigma _ {i} ^ {P} = PH}eu{\ displaystyle i}eu{\ displaystyle i}
Avem includerea: PH PSPACE . Egalitatea dintre PH și PSPACE nu este cunoscută. Dar egalitatea ar presupune că ierarhia polinomială se prăbușește.
⊆{\ displaystyle \ scriptstyle \ subseteq}
În special, dacă , atunci , adică : ierarhia polinomială se prăbușește la nivelul 1. Prin urmare, nu credem că ierarhia polinomială se prăbușește la nivelul 1 (aceasta este întrebarea P = NP ).
P=NUP{\ displaystyle P = NP}NUP=vs.oNUP{\ displaystyle NP = coNP}Σ1P=Π1P{\ displaystyle \ Sigma _ {1} ^ {P} = \ Pi _ {1} ^ {P}}
Clasele probabilistice
Și a fost legătura cu clasa probabilistică BPP : este teorema Sipser-Gács-Lautemann . Au fost de asemenea studiate relațiile dintre PH și clasa de complexitate cuantică BQP .
BPP⊆Σp2∩Πp2{\ displaystyle BPP \ subseteq \ Sigma _ {p} ^ {2} \ cap \ Pi _ {p} ^ {2}}
Bibliografie
-
AR Meyer și LJ Stockmeyer . Problema echivalenței pentru expresii regulate cu pătrat necesită spațiu exponențial. În Proceedings of the 13th IEEE Symposium on Switching and Automata Theory , pp. 125–129, 1972. Articolul care a introdus ierarhia.
-
LJ Stockmeyer . Ierarhia timp-polinom . Informatică teoretică , vol.3, pp. 1-22, 1976.
-
(ro) Christos Papadimitriou , Computational Complexity , Addison-Wesley ,1993( ISBN 978-0-201-53082-7 )Cap. 17. Ierarhia polinomială , pp. 409–438.
-
(ro) Michael R. Garey și David S. Johnson , Computers and Intractability: A Guide to Theory of NP-Completeness , New York, WH Freeman,1979, 338 p. ( ISBN 0-7167-1045-5 ) , „Secțiunea 7.2: Ierarhia polinomială” , p. 161–167.
- (ro) Sanjeev Arora și Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , cap. 5 („Ierarhia și alternanța polinomială”)
Link extern
Vezi și tu
Referințe
-
(în) Sipser, Introducere în teoria calculelor
-
(în) Scott Aaronson , „BQP și ierarhia polinomială” în STOC ,
2010, p. 141-150.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">