SC (complexity)
In
deterministic Turing machine in polynomial time (class P) and polylogarithmic space (class PolyL) (that is, O
((log n)k) space for some constant k). It may also be called DTISP(poly, polylog), where DTISP stands for deterministic time and space. Note that the definition of SC differs from P ∩ PolyL, since for the former, it is required that a single algorithm runs in both polynomial time and polylogarithmic space; while for the latter, two separate algorithms will suffice: one that runs in polynomial time, and another that runs in polylogarithmic space. (It is unknown whether SC and P ∩ PolyL are equivalent).
DCFL, the strict subset of context-free languages recognized by deterministic pushdown automata, is contained in SC, as shown by Cook in 1979.[2] It is open if all context-free languages can be recognized in SC, although they are known be in P ∩ PolyL.[3]
It is open if directed st-connectivity is in SC, although it is known to be in P ∩ PolyL (because of a DFS algorithm and Savitch's theorem). This question is equivalent to NL ⊆ SC.
derandomization result that both are contained in SC.[4] In other words, given polylogarithmic space, a deterministic machine can simulate logarithmic space probabilistic algorithms.