Polinom hiyerarşi
Olarak karmaşıklık teorisi , polinom hiyerarşi bir hiyerarşi karmaşıklık sınıflarının sınıflarının kavramını uzanan P , NP , ko-NP . PH sınıfı , polinom hiyerarşisinin tüm sınıflarının birleşimidir.
Tanımlar
Polinom hiyerarşisinin sınıflarının birkaç eşdeğer tanımı vardır.
Nicelik belirteçlerinin bir alternatifi olarak
Hiyerarşi, evrensel ( ) ve varoluşsal ( ) nicelik belirteçleri kullanılarak tanımlanabilir . Her şeyden önce, herhangi bir polinom ve herhangi bir dil için tanımlarız
∀{\ displaystyle \ forall}∃{\ displaystyle \ var} p{\ displaystyle p}L{\ displaystyle L}
∃pL: ={x∈{0,1}∗ | (∃w∈{0,1}≤p(|x|))⟨x,w⟩∈L}{\ displaystyle \ var ^ {p} L: = \ sol \ {x \ içinde \ {0,1 \} ^ {*} \ sol | \ \ sol (\ \ {0,1 \} içinde \ var ^ {\ leq p (| x |)} \ sağ) \ langle x, w \ rangle \ in L \ right. \ sağ \}},
Bu dizi, tam kelime kümesini içeren bir kelime var olan kelime, bu x uzunluğunda polinom boyutta olan . Sezgisel olarak, kelime , nispeten küçük bir sertifika için bir sertifika rolü oynar . Aynı şekilde tanımlıyoruz
∃pL{\ displaystyle \ var ^ {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 |)} \ sağ) \ langle x, w \ rangle \ in L \ right. \ sağ \}}.
Bu tanımları dil sınıflarına genişletiyoruz VS{\ displaystyle {\ mathcal {C}}}
∃PVS: ={∃pL | p bir polinomdur ve L∈VS}{\ displaystyle \ var ^ {\ rm {P}} {\ mathcal {C}}: = \ sol \ {\ var ^ {p} L \ | \ p {\ mbox {bir polinomdur ve}} L \ içinde {\ mathcal {C}} \ sağ \}}
∀PVS: ={∀pL | p bir polinomdur ve L∈VS}{\ displaystyle \ forall ^ {\ rm {P}} {\ mathcal {C}}: = \ left \ {\ forall ^ {p} L \ | \ p {\ mbox {bir polinomdur ve}} L \ in {\ mathcal {C}} \ sağ \}}
Şimdi, polinom hiyerarşisinin sınıflarını aşağıdaki gibi tümevarım yoluyla tanımlayabiliriz:
Σ0P: =Π0P: =P{\ displaystyle \ Sigma _ {0} ^ {\ rm {P}}: = \ Pi _ {0} ^ {\ rm {P}}: = {\ rm {P}}}
Σk+1P: =∃PΠkP{\ displaystyle \ Sigma _ {k + 1} ^ {\ rm {P}}: = \ var ^ {\ 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∈DEĞİLΣkP{\ displaystyle {\ rm {PH}} = {\ underet {k \ in \ mathbb {N}} {\ bigcup}} \ Sigma _ {k} ^ {\ rm {P}}}
Özellikle ve .
DEĞİLP=Σ1P{\ displaystyle {\ rm {NP}} = \ Sigma _ {1} ^ {\ rm {P}}}vsÖDEĞİLP=Π1P{\ displaystyle {\ rm {coNP}} = \ Pi _ {1} ^ {\ rm {P}}}
Oracle makineleri ile
Polinom hiyerarşi, oracle ile Turing makinesi kullanılarak da tanımlanabilir . karmaşıklık kehaneti ile artan karmaşıklık makinelerinin karar verebileceği sorunlar sınıfını ifade eder .
ATB{\ displaystyle A ^ {B}}AT{\ displaystyle A}B{\ displaystyle B}
Biz poz veriyoruz
Δ0P=Σ0P=Π0P=P{\ displaystyle \ Delta _ {0} ^ {P} = \ Sigma _ {0} ^ {P} = \ Pi _ {0} ^ {P} = {\ mbox {P}}}O zaman tüm i ≥ 0 için:
Δben+1P: =PΣbenP{\ displaystyle \ Delta _ {i + 1} ^ {P}: = {\ mbox {P}} ^ {\ Sigma _ {i} ^ {P}}}
Σben+1P: =NPΣbenP{\ displaystyle \ Sigma _ {i + 1} ^ {P}: = {\ mbox {NP}} ^ {\ Sigma _ {i} ^ {P}}}
Πben+1P: =ortak NPΣbenP{\ displaystyle \ Pi _ {i + 1} ^ {P}: = {\ mbox {co-NP}} ^ {\ Sigma _ {i} ^ {P}}}
Alternatif makinelerle
Polinom hiyerarşi, alternatif Turing makineleri kullanılarak tanımlanabilir . herhangi bir yürütmenin aynı tipteki (varoluşsal veya evrensel) konfigürasyonların i dizilerinden oluştuğu, yalnızca varoluşsal konfigürasyonları içeren ilk sekansın olduğu, polinom zamanda alternatif bir Turing makinesi tarafından karar verilen diller sınıfıdır. Tanımı benzerdir ancak ilk paketteki konfigürasyonlar evrenseldir.
ΣbenP{\ displaystyle \ Sigma _ {i} ^ {P}}ΠbenP{\ displaystyle \ Pi _ {i} ^ {P}}
Sorun örnekleri
Önermeler mantığının bir formül minimal olsun hiçbir kısa eşdeğer formüller varsa olduğunu, bir olduğunu algoritmik problemi de .
Σ2P{\ displaystyle \ Sigma _ {2} ^ {P}}
Özellikleri
Çöküşle ilgili soru
Polinom hiyerarşisine dahil olan diğer bir önemli özellik şudur: Bu, eğer bir seviyede iki sınıf eşitse, o zaman tüm "yukarıdaki" sınıfların eşit olduğu anlamına gelir . Daha sonra "polinom hiyerarşisinin düzeydeki çöküşünden" bahsediyoruz .
∀ben,ΣbenP=ΠbenP⇒ΣbenP=PH{\ displaystyle \ forall i, \ Sigma _ {i} ^ {P} = \ Pi _ {i} ^ {P} \ Rightarrow \ Sigma _ {i} ^ {P} = PH}ben{\ displaystyle i}ben{\ displaystyle i}
Dahil etme imkanımız var: PH PSPACE . PH ve PSPACE arasındaki eşitlik bilinmemektedir. Ancak eşitlik, polinom hiyerarşisinin çöktüğü anlamına gelir.
⊆{\ displaystyle \ scriptstyle \ subseteq}
Özellikle, eğer öyleyse , yani : polinom hiyerarşisi 1. seviyede çöker. Bu nedenle, 1. seviyede polinom hiyerarşisinin çöktüğünü düşünmüyoruz (bu, P = NP sorusudur ).
P=DEĞİLP{\ displaystyle P = NP}DEĞİLP=vsÖDEĞİLP{\ displaystyle NP = coNP}Σ1P=Π1P{\ displaystyle \ Sigma _ {1} ^ {P} = \ Pi _ {1} ^ {P}}
Olasılık sınıfları
Ve bu olasılık sınıf ile bağlantı oldu BPP : olan teoremi Sipser-Gács-Lautemann . PH ve kuantum karmaşıklık sınıfı BQP arasındaki ilişkiler de incelenmiştir.
BPP⊆Σp2∩Πp2{\ displaystyle BPP \ subseteq \ Sigma _ {p} ^ {2} \ cap \ Pi _ {p} ^ {2}}
Kaynakça
-
AR Meyer ve LJ Stockmeyer . Kare Alma ile Düzenli İfadeler için Eşdeğerlik Problemi Üstel Uzay Gerektirir. Anahtarlama ve Otomata Teorisi üzerine 13. IEEE Sempozyumu Bildirilerinde , s. 125–129, 1972. Hiyerarşiyi tanıtan makale.
-
LJ Stockmeyer . Polinom zaman hiyerarşisi . Teorik Bilgisayar Bilimi , cilt 3, s. 1–22, 1976.
-
(en) Christos Papadimitriou , Hesaplamalı Karmaşıklık , Addison-Wesley ,1993( Mayıs ISBN 978-0-201-53082-7 )Çatlak. 17. Polinom hiyerarşisi , s. 409–438.
-
(en) Michael R. Garey ve David S. Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness , New York, WH Freeman,1979, 338 s. ( ISBN 0-7167-1045-5 ) , "Bölüm 7.2: Polinom Hiyerarşisi" , s. 161–167.
- (tr) Sanjeev Arora ve Boaz Barak , Hesaplamalı Karmaşıklık: Modern Bir Yaklaşım , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , böl. 5 ("Polinom hiyerarşisi ve değişim")
Dış bağlantı
Ayrıca görün
Referanslar
-
(inç) Sipser, Hesaplama Teorisine Giriş
-
(in) Scott Aaronson , "BQP ve polinom hiyerarşisi" içinde STOC ,
2010, s. 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;">