SC (complexity)

In computational complexity theory, SC (Steve's Class, named after Stephen Cook) [ [http://qwiki.stanford.edu/wiki/Complexity_Zoo:S#sc Complexity Zoo: SC] ] is the complexity class of problems solvable by a deterministic Turing machine in polynomial time and polylogarithmic space (that is, O(log^k "n") space for some constant "k"). It may also be called DTISP(poly, polylog), where DTISP stands for "deterministic time and space".

DCFL, the strict subset of context-free languages recognized by deterministic pushdown automata, is contained in SC, as shown by Cook in 1979. [S. A. Cook. Deterministic CFL's are accepted simultaneously in polynomial time and log squared space. Proceedings of ACM STOC'79, pp. 338–345. 1979.]

RL and BPL are classes of problems acceptable by probabilistic Turing machines in logarithmic space and polynomial time. Nisan showed in 1992 the weak derandomization result that both are contained in SC. [N. Nisan. RL is contained in SC, Proceedings of ACM STOC'92, pp. 619-623, 1992.] In other words, given "polylogarithmic" space, a deterministic machine can simulate "logarithmic" space probabilistic algorithms.

References