S2P (Complexitat)

En teoria de la complexitat, la classe de complexitat SP
2 és la classe de complexitat intermèdia entre el primer i segon nivell de la jerarquia polinòmica. Un llenguatge L és a SP
2 si existeix un predicat P de temps polinòmic tal que:

• si $x\in L$, llavors existeix un y tal que per tot z, $P(x,y,z)=1$
• si $x\notin L$, llavors existeix un z tal que per tot y, $P(x,y,z)=0$

on y i z son polinomis de x.

Relació amb d'altres classes

A partir de la definició és immediat veure que SP
2 és tancada per unions, interseccions i complement. Comparant la definició amb la de $\Sigma _{2}^{P}$i $\Pi _{2}^{P}$, es segueix que SP
2 està contingut dins de $\Sigma _{2}^{P}\cap \Pi _{2}^{P}$. Aquesta inclusió es pot augmentar a ZPP^NP.

Tot llenguatge a NP també pertany a SP
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 SP
2, P(x,y,z) pel mateix llenguatge que ignori z i es comporti igual que el verificador V. Pel mateix raonament, co-NP pertany a SP
2 .

També es pot demostrar que SP
2 conté MA i $\Delta _{2}^{P}$i de forma més general $P^{{\mathsf {S}}_{2}^{P}}={\mathsf {S}}_{2}^{P}$.