In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, SC (Steve's Class, named after
Stephen Cook
Stephen Arthur Cook (born December 14, 1939) is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor at the Univ ...
) is the
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
of problems solvable by a
deterministic Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
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 language
In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).
Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by ...
s recognized by
deterministic pushdown automata In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages.
...
, 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 if directed
st-connectivity
In computer science, st-connectivity or STCON is a decision problem asking, for vertices ''s'' and ''t'' in a directed graph, if ''t'' is reachable from ''s''.
Formally, the decision problem is given by
:.
Complexity
On a sequential computer ...
is in SC, although it is known to be in P ∩ PolyL (because of a DFS algorithm and
Savitch's theorem
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity. It states that for any function f\in\Omega(\log(n)),
:\mathsf\left(f\lef ...
). This question is equivalent to
NL ⊆ SC.
RL and
BPL are classes of problems acceptable by
probabilistic Turing machines
In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turi ...
in logarithmic space and polynomial time.
Noam Nisan
Noam Nisan ( he, נעם ניסן; born June 20, 1961) is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game th ...
showed in 1992 the weak
derandomization
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
result that both are contained in SC.
[.] In other words, given ''polylogarithmic'' space, a deterministic machine can simulate ''logarithmic'' space probabilistic algorithms.
References
{{DEFAULTSORT:Sc (Complexity)
Complexity classes