The class of decision problems solvable by a Turing machine that uses time O(t(n)) and space O(s(n)) simultaneously.
Thus SC = DTISP(poly,polylog) for example.
Defined in [Nis92], where it was also shown that for all space-constructible s(n)=Ω(log n), BPSPACE(s(n)) is contained in DTISP(2O(s(n)),s2(n)).
(Named in honor of Stephen Cook.)
The class of decision problems solvable by a Turing machine that simultaneously uses polynomial time and polylogarithmic space.
Note that SC might be smaller than P ∩ polyL, since for the latter, it suffices to have two separate algorithms: one polynomial-time and the other polylogarithmic-space.
Deterministic context-free languages (DCFLs) can be recognized in SC [Coo79].
SC contains RL and BPL [Nis92].
SC equals DTISP(poly,polylog) by definition.