SC (complexity)

Article summary

In computational complexity theory, SC (Steve's Class, named after Stephen Cook) is the complexity class of problems solvable by a 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. 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. It is open if all context-free languages can be recognized in SC, although they are known be in P ∩ PolyL. It is open whether directed st-connectivity is in SC, although it is known to be in P ∩ PolyL: depth first search solves it in polynomial time and Savitch's theorem provides a solution on space O(\log^2 n) . This question is equivalent to NL ⊆ SC. RL and BPL are classes of problems acceptable by probabilistic Turing machines in logarithmic space and polynomial time.…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.