# SC (complexity)

In computational complexity theory, **SC** (Steve's Class, named after Stephen Cook)^{[1]} 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*. 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 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**.

**RL** and **BPL** are classes of problems acceptable by probabilistic Turing machines in logarithmic space and polynomial time. Noam Nisan showed in 1992 the weak derandomization result that both are contained in **SC**.^{[3]} In other words, given *polylogarithmic* space, a deterministic machine can simulate *logarithmic* space probabilistic algorithms.

## References[edit]

**^***Complexity Zoo*: SC**^**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.**^**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.

P ≟ NP | This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it. |