Mostra la font per a S2P (Complexitat)

En [[Complexitat computacional|teoria de la complexitat]], la [[classe de complexitat]] '''S{{su|p=''P''|b=2}}''' és la [[classe de complexitat]] intermèdia entre el primer i segon nivell de la [[jerarquia polinòmica]]. Un [[Llenguatge formal|llenguatge]] ''L'' és a '''S{{su|p=''P''|b=2}} si existeix un predicat ''P'' de [[temps polinòmic]] tal que:'''

* si <math>x\in L</math>, llavors existeix un ''y'' tal que per tot ''z,'' <math> P(x,y,z)=1</math>
* si <math>x\notin L</math>, llavors existeix un ''z'' tal que per tot ''y,'' <math> P(x,y,z)=0</math>

on ''y'' i ''z'' son polinomis de ''x.''

== Relació amb d'altres classes ==
A partir de la definició és immediat veure que '''S{{su|p=''P''|b=2}} és tancada per [[Unió|unions]], [[Intersecció|interseccions]] i [[Complementari|complement]]. Comparant la definició amb la de''' <math>\Sigma_{2}^P</math>i <math>\Pi_{2}^P</math>, es segueix que '''S{{su|p=''P''|b=2}}''' està contingut dins de <math>\Sigma_{2}^P \cap \Pi_{2}^P</math>. Aquesta inclusió es pot augmentar a '''[[ZPP (Complexitat)|ZPP]]<sup>NP</sup>'''.<ref>{{Ref-publicació|article=S2p⊆ZPPNP|publicació=Journal of Computer and System Sciences|llengua=en|url=https://www.sciencedirect.com/science/article/pii/S002200000600105X|volum=73|exemplar=1|data=2007-02-01|pàgines=25–35|doi=10.1016/j.jcss.2003.07.015|issn=0022-0000}}</ref>

Tot llenguatge a [[NP (Complexitat)|NP]] també pertany a '''S{{su|p=''P''|b=2}}. Per la definició, un llenguatge ''L'' és a NP, [[si i només si]] existeix un verificador en temps polinòmic ''V''(''x'',''y'') tal que per cada ''x'' a ''L'' existeix ''y'' pel qual ''V'' respon cert, i per tot ''x'' no a ''L'', ''V'' respon sempre fals. Però aquest verificador es pot transformar fàcilment en un predicat de S{{su|p=''P''|b=2}}, ''P''(''x'',''y'',''z'') pel mateix llenguatge que ignori ''z'' i es comporti igual que el verificador ''V''. Pel mateix raonament, [[Co-NP (Complexitat)|co-NP]] pertany a S{{su|p=''P''|b=2}} .''' 

'''També es pot demostrar que S{{su|p=''P''|b=2}} conté [[MA (Complexitat)|MA]] i''' <math>\Delta_{2}^P</math>i de forma més general <math>P^{\mathsf S_2^P}=\mathsf S_2^P</math>.<ref>{{Ref-publicació|cognom=Sundaram|nom=R.|cognom2=Russell|nom2=A.|article=Symmetric alternation captures BPP|publicació=computational complexity|llengua=en|url=https://link.springer.com/article/10.1007/s000370050007|volum=7|exemplar=2|data=1998-11-01|pàgines=152–162|doi=10.1007/s000370050007|issn=1420-8954}}</ref>

== Referències ==
{{referències}}

{{classes de complexitat}}

{{Autoritat}}

[[Categoria:Classes de complexitat]]