S2P (složitost) - S2P (complexity)

v teorie výpočetní složitosti, S^P
₂ je třída složitosti, mezi první a druhou úrovní polynomiální hierarchie. Jazyk L je v ${ displaystyle { mathsf {S}} _ {2} ^ {P}}$ pokud existuje predikát polynomiálního času P takhle

• Li ${ displaystyle x v L}$, pak existuje a y takové, že pro všechny z, ${ displaystyle P (x, y, z) = 1}$,
• Li ${ displaystyle x notin L}$, pak existuje a z takové, že pro všechny y, ${ displaystyle P (x, y, z) = 0}$,

kde velikost y a z musí být polynom z X.

Vztah k dalším třídám složitosti

Z definice je bezprostřední, že S^P
₂ je uzavřena pod odbory, křižovatkami a doplňky. Porovnání definice s definicí ${ displaystyle Sigma _ {2} ^ {P}}$ a ${ displaystyle Pi _ {2} ^ {P}}$, okamžitě také vyplývá, že S^P
₂ je obsažen v ${ displaystyle Sigma _ {2} ^ {P} cap Pi _ {2} ^ {P}}$. Toto začlenění lze ve skutečnosti posílit ZPP^NP.^[1]

Každý jazyk v NP také patří S^P
₂. Podle definice jazyk L je v NP, právě když existuje ověřovač polynomiálního času PROTI(X,y), takže pro každého X v L tady existuje y pro který PROTI odpovědi pravdivé a takové, že pro každého X ne v L, PROTI vždy odpoví nepravdivě. Ale takový ověřovatel lze snadno transformovat na S^P
₂ predikát P(X,y,z) pro stejný jazyk, který ignoruje z a jinak se chová stejně PROTI. Ze stejného důvodu, co-NP patří S^P
₂. Tyto přímé inkluze mohou být posíleny, aby ukázaly, že třída S^P
₂ obsahuje MA (zevšeobecněním Sipser – Lautemannova věta ) a ${ displaystyle Delta _ {2} ^ {P}}$ (obecněji, ${ displaystyle P ^ {{ mathsf {S}} _ {2} ^ {P}} = { mathsf {S}} _ {2} ^ {P}}$).

Karp – Liptonova věta

Verze Karp – Liptonova věta uvádí, že pokud každý jazyk v NP má polynomiální velikosti obvodů pak polynomiální časová hierarchie se zhroutí na S.^P
₂. Tento výsledek vede k posílení Kannan Věta: je známo, že S^P
₂ není obsažen v VELIKOST(n^k) pro všechny pevnék.

Symetrická hierarchie

Jako rozšíření je možné definovat ${ displaystyle { mathsf {S}} _ {2}}$ jako operátor tříd složitosti; pak ${ displaystyle { mathsf {S}} _ {2} P = { mathsf {S}} _ {2} ^ {P}}$. Iterace ${ displaystyle S_ {2}}$ operátor získá „symetrickou hierarchii“; sjednocení takto vytvořených tříd se rovná Polynomiální hierarchie.

Reference

• Canetti, Ran (1996). "Více o BPP a hierarchii polynomiálního času". Dopisy o zpracování informací. Elsevier. 57 (5): 237–241. doi:10.1016/0020-0190(96)00016-6.
• Russell, Alexander; Sundaram, Ravi (1998). Msgstr "Symetrické střídání zachycuje BPP". Výpočetní složitost. Birkhäuser Verlag. 7 (2): 152–162. doi:10,1007 / s000370050007. ISSN  1016-3328. S2CID  15331219.

externí odkazy

• Složitost Zoo: S₂P
• Třída složitosti týdne: S₂^P, Lance Fortnow, 28. srpna 2002.