0x301 Complexity

Complexity

Complexity zoo has a good explanation for each of the complexity classes.

Reference: Wikipedia

Time Complexity

Definition (time complexity) Let $M$ be a deterministic Turing machine that halts on all inputs. The time complexity of $M$ is the function $f: \mathcal{N} \to \mathcal{N}$ where $f(n)$ is the max number of steps that $M$ uses on any input of length $n$

  • P: decidable in polynomial times
  • NP: verifiable in polynomial times
  • co-NP: complement is NP
  • NP-complete: A NP problem is NP-complete if any NP can be reduced to this problem in polynomial times
  • NP-hard: A problem if NP-hard if any NP can be reduced to this problem in polynomial times
  • EXPTIME: decidable in exponential time

Theorems:

  • Cook-Levin: Any NP problems can be reduced in polynomial times to Boolean satisfiability problem (Boolean satisfiability is NP-complete)

Space Complexity

Definitions

  • PSPACE: decidable using polynomial space
  • NPSPACE: verifiable in polynomial space

Theorems:

  • Savitch: NPSPACE can be reduced to PSPACE (with square space complexity bound)

Quantum Complexity

Definitions

  • BQP: decidable by quantum computer in polynomial time within 1/3 error probability.