S2P (Complexitat)

En teoria de la complexitat, la classe de complexitat SPlantilla:Su és la classe de complexitat intermèdia entre el primer i segon nivell de la jerarquia polinòmica. Un llenguatge L és a SPlantilla:Su 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 SPlantilla:Su és tancada per unions, interseccions i complement. Comparant la definició amb la de ${\mathrm{\Sigma }}_2^P$i ${\mathrm{\Pi }}_2^P$, es segueix que SPlantilla:Su està contingut dins de ${\mathrm{\Sigma }}_2^P\cap {\mathrm{\Pi }}_2^P$. Aquesta inclusió es pot augmentar a ZPP^NP.

Tot llenguatge a NP també pertany a SPlantilla:Su. 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 SPlantilla:Su, 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 SPlantilla:Su .

També es pot demostrar que SPlantilla:Su conté MA i ${\mathrm{\Delta }}_2^P$i de forma més general $P^{{𝖲}_2^P}={𝖲}_2^P$.