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