En teoria de la complexitat, la classe de complexitat SC (classe de Steve, per Stephen Cook) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en temps polinòmic (classe P) i en espai polilogarítmic (classe PolyL) O((log n)k per una constant k.
La definició de la classe SC és diferent de P ∩ PolyL, ja que la classe SC cal que un algorisme compleixi les dues restriccions juntes i per la intersecció dos algorismes separats és suficient, un algorisme funciona en temps polinòmic i un segon algorisme funciona en espai polilogarítmic.
Relació amb d'altres classes La classe DCFL, el subconjunt estricte dels llenguatges lliures del context reconeixibles per un autòmat amb pila, està continguda dins de SC.
Se sap que la classe SC conté la classe RL i BPL.
Per definició, la classe DTISP (poly, polylog) és igual a SC.
Referències
Categoria:Classes de complexitat