En teoria de la complexitat, la classe de complexitat S és la classe de complexitat intermèdia entre el primer i segon nivell de la jerarquia polinòmica. Un llenguatge L és a S si existeix un predicat P de temps polinòmic tal que:
si , llavors existeix un y tal que per tot z, si , llavors existeix un z tal que per tot y,
on y i z son polinomis de x.
Relació amb d'altres classes A partir de la definició és immediat veure que S és tancada per unions, interseccions i complement. Comparant la definició amb la de i , es segueix que S està contingut dins de . Aquesta inclusió es pot augmentar a ZPPNP.
Tot llenguatge a NP també pertany a S. 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, 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 S .
També es pot demostrar que S conté MA i i de forma més general .
Referències
Categoria:Classes de complexitat