SC (complejidad)

En la teoría de la complejidad computacional , SC (Steve's Class, nombrada en honor a Stephen Cook ) ^{[ 1 ]} es la clase de complejidad de problemas resolubles por una máquina de Turing determinista en tiempo polinomial (clase P ) y espacio polilogarítmico (clase PolyL ) (es decir, espacio O ((log n ) ^{k ) para alguna constante} k ). También puede denominarse DTISP(poly, polylog) , donde DTISP significa tiempo y espacio deterministas . La definición de SC difiere de P ∩ PolyL , ya que para la primera se requiere que un único algoritmo se ejecute tanto en tiempo polinomial como en espacio polilogarítmico; mientras que para la segunda bastan dos algoritmos separados: uno que se ejecute en tiempo polinomial y otro que se ejecute en espacio polilogarítmico. Se desconoce si SC y P ∩ PolyL son equivalentes.

DCFL , el subconjunto estricto de lenguajes libres de contexto reconocidos por autómatas de pila deterministas , está contenido en SC , como demostró Cook en 1979. ^{[ 2 ]} Es un problema abierto si todos los lenguajes libres de contexto pueden ser reconocidos en SC , aunque se sabe que están en P ∩ PolyL . ^{[ 3 ]}

Está abierto si la conectividad st dirigida está en SC , aunque se sabe que está en P ∩ PolyL : la búsqueda en profundidad la resuelve en tiempo polinomial y el teorema de Savitch proporciona una solución en espacio${\displaystyle O(\log ^{2}n)}$. Esta pregunta es equivalente a NL ⊆ SC . ^{[ 4 ]}

RL y BPL son clases de problemas aceptables para máquinas de Turing probabilísticas en espacio logarítmico y tiempo polinomial. Noam Nisan demostró en 1992 el resultado de desaleatorización débil que indica que ambos están contenidos en SC . ^{[ 5 ]} En otras palabras, dado un espacio polilogarítmico , una máquina determinista puede simularalgoritmos probabilísticos en espacio logarítmico .