## Complexity Class Brief Definitions

### Language Classes

```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
```

### Function Classes

```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
```

### Hierarchies

```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
```

### Notes

```  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