Incomputational complexity theory,SC (Steve's Class, named afterStephen Cook)^[1] is thecomplexity class of problems solvable by adeterministic Turing machine in polynomial time (classP) and polylogarithmic space (classPolyL) (that is,O((logn)^k) space for some constantk). It may also be calledDTISP(poly, polylog), whereDTISP stands fordeterministic time and space. The definition ofSC differs fromP ∩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 whetherSC andP ∩PolyL are equivalent.

DCFL, the strict subset ofcontext-free languages recognized bydeterministic pushdown automata, is contained inSC, as shown by Cook in 1979.^[2] It is open if all context-free languages can be recognized inSC, although they are known be inP ∩PolyL.^[3]

It is open whether directedst-connectivity is inSC, although it is known to be inP ∩PolyL:depth first search solves it in polynomial time andSavitch's theorem provides a solution on space${\displaystyle O({\log }^{2}n)}$. This question is equivalent toNL ⊆SC.^[4]

RL andBPL are classes of problems acceptable byprobabilistic Turing machines in logarithmic space and polynomial time.Noam Nisan showed in 1992 the weakderandomization result that both are contained inSC.^[5] In other words, givenpolylogarithmic space, a deterministic machine can simulatelogarithmic space probabilistic algorithms.

• Theoretical computer science stubs
• Complexity classes

• CS1 maint: location missing publisher
• Articles with short description
• Short description is different from Wikidata
• All stub articles