Class Description

DTISP(t(n),s(n)): Simultaneous t(n)-Time and s(n)-Space

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)).

Linked From

SC: Steve's Class

(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 PpolyL, 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.

More about...