Class: Brief description
P: the set of languages accepted by deterministic Turing machines
in polynomial time
NP: the set of languages accepted by nondeterministic Turing machines
in polynomial time
co-NP: the set of languages rejected by nondeterministic Turing machines
in polynomial time
PSPACE: the set of languages accepted by deterministic Turing machines
in polynomial space
NPSPACE: the set of languages accepted by nondeterministic Turing machines
in polynomial space
LOGSPACE: the set of languages accepted by deterministic Turing machines
in logarithmic space
NLOGSPACE:the set of languages accepted by nondeterministic Turing machines
in logarithmic space
EXP: the set of languages accepted by deterministic Turing machines
in t(n)=2^cn time
NEXP: the set of languages accepted by nondeterministic Turing machines
in t(n)=2^cn time
PEXP: the set of languages accepted by deterministic Turing machines
in t(n)=2^p(n) time
NPEXP: the set of languages accepted by nondeterministic Turing machines
in t(n)=2^p(n) time
UP: the set of languages accepted by unambiguous nondeterministic
Turing machines, that have at least one accepting computation
on any input, in polynomial time
PP: the set of languages accepted by probabilistic
polynomial-time Turing machines
(not proved random = pseudo random)
BPP: the set of languages accepted by bounded probabilistic
polynomial-time Turing machines (balanced probability)
RP: the set of languages accepted by random probabilistic
polynomial-time Turing machines (one sided probability)
co-RP: the set of languages accepted by RP machines with accept
and reject probabilities reversed
ZPP: RP intersection co-RP, the set of languages accepted by
zero probability of error polynomial-time Turing machines
PF: the set of functions computed by deterministic Turing machines
in polynomial time
NPF: the set of functions computed by nondeterministic Turing machines
in polynomial time
PSPACEF: the set of functions computed by deterministic Turing machines
in polynomial space
#P: the set of functions that enumerate the number of accepting
computations of polynomial-time nondeterministic Turing machines
PH: the union of classes known as the polynomial-time hierarchy BH: the union of classes known as the Boolean hierarchy QH: the union of classes known as the query hierarchy
An alphabet is a finite set of symbols.
A string is a finite concatenation of symbols from an alphabet
A language is a set of strings.
A class is a set of languages.
A hierarchy is a set of classes with relationships.
"polynomial time" means there is a fixed polynomial p(n) and for each
string x, accepted by a machine, the number of steps the machine takes
is bounded by p(n).
The "n" is the length of an input string x denoted |x|.
In general the time bound is expressed an t(f(n)) as in EXP
where t(n)=2^cn .
"logarithmetic space" means there is a fixed f(n) and for each
string x, accepted by a machine, the number of temporary storage
places for symbols is bounded by f(n)= c*log(n).
Let L be a language defined as a set L that is a subset of sigma star,
for some finite alphabet sigma.
L is the set of strings accepted by some restriction of a Turing machine.
P is a set of languages where the restriction is a deterministic Turing
machine with moves bounded by a polynomial in the length of x, |x|
P = {L | language L is accepted by a deterministic Turing machine
in polynomial time}
co-P = {L | complement of L is in P}
Note: P is closed under complementation but if NP = co-NP then
PH collapses.
#P = {f | f(x) = number of accepting paths in M(x) for some NP machine M}
L in BPP implies there exists a set A in P, such that
x in L implies Prob(y)[(x,y) in A] >= 1/2 and
x not in L implies Prob(y)[(x,y) not in A] >= 1/2
L in RP implies there exists a set A in P, such that
x in L implies Prob(y)[(x,y) in A] >= 1/2 and
x not in L implies Prob(y)[(x,y) not in A] = 1
(no error on rejection)
L in co-RP implies there exists a set A in P, such that
x in L implies Prob(y)[(x,y) in A] = 1 and
x not in L implies Prob(y)[(x,y) not in A] >= 1/2
(no error on accepting)
Where y is chosen randomly over {0,1}^q for some q bounded by
a polynomial in |x| and A is a set of ordered pairs, x from L
and y from {0,1}^q.
Probabilities greater than 1/2 + 1/( O(2^n) ) can be amplified to be
arbitrarily close to 1.0 using a polynomial number of tries.
Last updated 11/30/03