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 PPolyL, 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 PPolyL 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 PPolyL (por causa de um algoritmo DFS e o teorema de Savitch). Esta pergunta é equivalente a NLSC.

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

  1. Complexity Zoo: SC
  2. S. A. Cook.
  3. 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 .