Complexity classes

@complexity

These are the complexity classes I have encountered so far.

Note that complexity classes are defined on decision problems. However, regular optimization problems can be translated into decision problems. For example, for some constraint satisfaction problem, the decision problem would be: "Is there a solution that satisfies given constraints?" A solution partitions the input into yes- and no-instances.

  • P (polynomial): decidable in polynomial time.
  • NP (non-deterministic polynomial): verifiable in polynomial time.
    • i.e. if someone gives you a correct solution (not an incorrect one!), can you verify its correctness?
  • NP-hard: at least as hard as any other problem in NP, i.e. all other NP problems can be reduced to this problem.
  • NP-Complete: both in NP and NP-hard.
    • N.B. a problem may be shown to be as hard as any other problem in NP, while there still does not currently exist a polynomial time algorithm to verify a correct solution.
    • N.B. if P=NP, then P=NP=NP-Complete

These classes are defined on randomized algorithms i.e. in terms of the probability of answering correctly or incorrectly (within proven error bounds).

  • BPP: bounded probabilistic polynomial time (akin to P)
    • It is conjectured that BPP=P, meaning that for these stochastic solutions there is also expected to be a determinstic solution!
    • Already deterministic algorithms shown for many problems in BPP
  • PP: (includes inherently intractable problems) (akin to NP)
  • PP-complete
  • PP-hard

Combinations of the P/NP classes with the PP classes; these are defined using the theoretical construct of Oracle Turing Machines:

  • $NP^{PP}$: "the class of problems which are verifiable in polynomial time on a machine that has access to an oracle deciding problems in PP" (p.40, Kwisthout TFCA lecture notes)
    • Computations in PP are then assumed to be for "free" because this class makes use of an oracle machine
  • $NP^{PP}-complete$: canonical satisfiability problem is E-MajSat.
  • $P^{NP^{PP}}$
  • $NP^{PP^{PP}}$