En la teoría de la complejidad computacional , SC (Clase de Steve, llamada así por Stephen Cook ) [1] es la clase de complejidad de problemas que se pueden resolver mediante una máquina de Turing determinista en tiempo polinomial (clase P ) y espacio polilogarítmico (clase PolyL ) (es decir, O ( (log n ) k ) espacio para alguna constante k ). También se le puede llamar DTISP (poly, polylog) , donde DTISP significa tiempo y espacio deterministas . Tenga en cuenta que la definición de SC difiere deP ∩ PolyL , ya que para el primero, se requiere que un solo algoritmo se ejecute tanto en tiempo polinomial como en espacio polilogarítmico; mientras que para el último, dos algoritmos separados serán suficientes: uno que se ejecuta en tiempo polinomial y otro que se ejecuta en espacio polilogarítmico. (Se desconoce si SC y P ∩ PolyL son equivalentes).
DCFL , el subconjunto estricto de lenguajes libres de contexto reconocidos por los autómatas pushdown deterministas , está contenido en SC , como lo demostró Cook en 1979. [2]
Está abierto si la conectividad st dirigida está en SC , aunque se sabe que está en P ∩ PolyL (debido a un algoritmo DFS y al teorema de Savitch ). Esta pregunta es equivalente a NL ⊆ SC .
RL y BPL son clases de problemas aceptables por máquinas de Turing probabilísticas en espacio logarítmico y tiempo polinomial. Noam Nisan mostró en 1992 el débilresultado de la desaleatorización de que ambos están contenidos en SC . [3] En otras palabras, dado elespacio polilogarítmico , una máquina determinista puede simularalgoritmos probabilísticos del espacio logarítmico .
Referencias
- ^ Zoológico de complejidad : SC
- ^ SA Cook. Las CFL deterministas se aceptan simultáneamente en tiempo polinomial y espacio logarítmico al cuadrado. Actas de ACM STOC'79, págs. 338–345. 1979.
- ^ Nisan, Noam (1992), "RL ⊆ SC", Actas del 24º Simposio de ACM sobre teoría de la computación (STOC '92) , Victoria, Columbia Británica, Canadá, págs. 619–623, doi : 10.1145 / 129712.129772.