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.