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.
Referências[editar | editar código-fonte]
- ↑ Complexity Zoo: SC
- ↑ S. A. Cook.
- ↑ Nisan, Noam (1992), «RL ⊆ SC», Proceedings of the 24th ACM Symposium on Theory of computing (STOC '92), Victoria, British Columbia, Canada, pp. 619–623, doi:10.1145/129712.129772.