SC (clase de complejidad)

En complejidad computacional, SC (Steve's Class, en español Clase de Steve en honor a Stephen Cook)^[1] es una clase de complejidad que incluye a los problemas resolubles por una máquina de Turing determinista en tiempo polinomial (clase P) y espacio polilogarítmico (clase PolyL) (esto es un espacio de orden O(log^k n) para alguna constante k). También es llamada DTISP(poly, polylog), donde DTISP significa deterministic time and space ("tiempo y espacio determinista"). Note que la clase SC está contenida estrictamente en la clase P ∩ PolyL, puesto que para la primera, se requiere que el algoritmo corra al mismo tiempo en tiempo polinomial y espacio polilogarítmico; mientras que para la segunda, dos algoritmos posiblemente distintos pueden separadamente satisfacer ambas condiciones.

Cook demostró en 1979 que los lenguajes libres de contexto deterministas, reconocidos por los autómatas con pila deterministas, están contenidos en SC.^[2]

Las clases RL y BPL contienen problemas aceptables por máquinas de Turing probabilísticas en espacio logarítmico y tiempo polinomial. Nisan demostró en 1992 que ambas clases están contenidas en SC.^[3] En otras palabras, dado un espacio polilogarítmico, una máquina determinista puede simular un algoritmo probabilista de espacio logarítmico.

Referencias

↑ ComplexityZoo: SC
↑ S. A. Cook. Deterministic CFL's are accepted simultaneously in polynomial time and log squared space. Proceedings of ACM STOC'79, pp. 338–345. 1979.
↑ N. Nisan. RL is contained in SC, Proceedings of ACM STOC'92, pp. 619-623, 1992.

Datos: Q7389363

[1] ComplexityZoo: SC

[2] S. A. Cook. Deterministic CFL's are accepted simultaneously in polynomial time and log squared space. Proceedings of ACM STOC'79, pp. 338–345. 1979.

[3] N. Nisan. RL is contained in SC, Proceedings of ACM STOC'92, pp. 619-623, 1992.

[1]

[2]

[3]