SC (complexidade)

Na teoria da complexidade computacional, SC (Steve Classe, em homenagem a Stephen Cook)[1] é a classe de complexidade dos problemas resolvidos por uma máquina de Turing determinística em tempo polinomial (classe P) e em espaço espaço polylogarithmic (classe PolyL) (isto é, O((log n)^k) espaço para alguma constante k). Ele também pode ser chamado DTISP(poli, polylog), onde DTISP significa determinística do tempo e do espaço. Note que a definição de SC é diferente de P ∩ PolyL, uma vez que, para os antigos, é necessário que o algoritmo é executado tanto em tempo polinomial e polylogarithmic espaço; enquanto que para o último, dois algoritmos será suficiente: um que é executado em tempo polinomial, e outro que é executado no polylogarithmic espaço. (Não se sabe se o PB e P ∩ PolyL são equivalentes).

DCFL, o subconjunto estrito de linguagens livre de contexto reconhecido pelo "deterministic pushdown automata", está contido em SC, como mostrado por Cook em 1979.[2]

É abrir-se dirigido st-conectividade é em SC, embora seja conhecido na P ∩ PolyL (por causa de um algoritmo DFS e o teorema de Savitch). Esta pergunta é equivalente a NL ⊆ SC.

RL e BPL são classes de problemas aceitável por máquinas de Turing probabilística em logarítmica espaço e tempo polinomial. Noam Nissan mostrou, em 1992, o fraco resultado conhecido como derandomization ("desrandomização") indica que ambos estão contidos em SC.[3] Em outras palavras, dada espaço polylogarithmic, um determinista da máquina pode simular logarítmica espaço probabilístico de algoritmos.