SC (Complexitat)
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.[1][2]
La definició de la classe SC és diferent de P ∩ PolyL, ja que la classe SC es requereix 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.[2]
Relació amb d'altres classes
[modifica]La classe DCFL, el subconjunt estricte dels llenguatges lliures del context reconeixibles per un autòmat amb pila, està continguda dins de SC.[3]
Se sap que la classe SC conté la classe RL i BPL.[4]
Per definició, la classe DTISP (poly, polylog) és igual a SC.
Referències
[modifica]- ↑ Computational complexity theory. Providence, R.I.: American Mathematical Society, 2004. ISBN 082182872X.
- ↑ 2,0 2,1 «Complexity Zoo:S - Complexity Zoo» (en anglès). Arxivat de l'original el 2016-08-27. [Consulta: 1r desembre 2018].
- ↑ Cook, Stephen A. «Deterministic CFL's are accepted simultaneously in polynomial time and log squared space». STOC '79 Proceedings of the eleventh annual ACM symposium on Theory of computing. ACM, 30-04-1979, pàg. 338–345. DOI: 10.1145/800135.804426.
- ↑ Nisan, Noam «RL⊆SC». STOC '92 Proceedings of the twenty-fourth annual ACM symposium on Theory of computing. ACM, 01-07-1992, pàg. 619–623. DOI: 10.1145/129712.129772.
| Considerades tractables | |
|---|---|
| Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
