Na teoria da complexidade computacional, SC (Steve Classe, em homenagem a Stephen Cook)Complexity Zoo: SC é 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.S. A. Cook.
É 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.. Em outras palavras, dada espaço polylogarithmic, um determinista da máquina pode simular logarítmica espaço probabilístico de algoritmos.
Referências
Categoria:Classes de complexidade