SC (complexity)
Encyclopedia
In computational complexity theory
, SC (Steve's Class, named after Stephen Cook
) 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 SC might be properly contained in P
PolyL, since for the former, it is required that the algorithm runs both in polynomial time and polylogarithmic space; while for the latter, two separate algorithms will suffice: One that runs in polynomial time, and another which runs in polylogarithmic space.
DCFL
, the strict subset of context-free language
s recognized by deterministic pushdown automata
, is contained in SC, as shown by Cook in 1979.
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. Nisan showed in 1992 the weak derandomization result that both are contained in SC. In other words, given polylogarithmic space, a deterministic machine can simulate logarithmic space probabilistic algorithms.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, SC (Steve's Class, named after Stephen Cook
Stephen Cook
Stephen Arthur Cook is a renowned American-Canadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity...
) is the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
of problems solvable by a deterministic Turing machine in polynomial time (class P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
) and polylogarithmic space (class PolyL
PolyL
In computational complexity theory, PolyL is the complexity class of decision problems that can be solved on a deterministic Turing machine whose required space is bounded by some polylogarithmic function in the size of the input...
) (that is, O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
((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 SC might be properly contained in P
PolyL, since for the former, it is required that the algorithm runs both in polynomial time and polylogarithmic space; while for the latter, two separate algorithms will suffice: One that runs in polynomial time, and another which runs in polylogarithmic space.DCFL
Deterministic context-free language
A deterministic context-free language is a formal language which is defined by a deterministic context-free grammar. The set of deterministic context-free languages is called DCFL and is identical to the set of languages accepted by a deterministic pushdown automaton.The set of deterministic...
, the strict subset of context-free language
Context-free language
In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...
s recognized by deterministic pushdown automata
Deterministic pushdown automaton
In automata theory, a pushdown automaton is a finite automaton with an additional stack of symbols; its transitions can take the top symbol on the stack and depend on its value, and they can add new top symbols to the stack....
, is contained in SC, as shown by Cook in 1979.
It is open if directed st-connectivity
ST-connectivity
In computer science and computational complexity theory, 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 :...
is in SC, although it is known to be in P
PolyL (because of a DFS algorithm and Savitch's theoremSavitch's theorem
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, states that for any function ƒ ≥ log,...
). This question is equivalent to NL
NL (complexity)
In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space....
⊆ SC.
RL and BPL
BPL (complexity)
In computational complexity theory, BPL , sometimes called BPLP , is the complexity class of problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with two-sided error...
are classes of problems acceptable by probabilistic Turing machines in logarithmic space and polynomial time. Nisan showed in 1992 the weak derandomization result that both are contained in SC. In other words, given polylogarithmic space, a deterministic machine can simulate logarithmic space probabilistic algorithms.