Skip to content

0x301 Complexity

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

complexity

1. Asymptotic Analysis

Definition (\(\Theta\)-notation) For a given function \(g(n)\), we denote by \(\Theta(g(n))\) the set of functions

\[\Theta(g(n)) = \{ f(n) | (\exists{c_1, c_2, n_0 > 0 })(\forall{n \geq n_0}) 0 \leq c_1 g(n) \leq f(n) \leq c_2g(n) \}\]

We say that \(g(n)\) is an asymptotically tight bound for \(f(n)\), it bounds the function from above and below

Definition (O-notation) For a given function \(g(n)\), we denote by \(O(g(n))\) the set of functions

\[O(g(n)) = \{ f(n) | (\exists{c, n_0 > 0})(\forall{n \geq n_0}) 0 \leq f(n) \leq cg(n) \}\]

This is an asymptotic upper bound.

Definition (\(\Omega\)-notation) For a given function \(g(n)\), we denote by \(\Omega(g(n))\) the set of functions

\[\Omega(g(n)) = \{ (\exists{c, n_0 > 0})(\forall{n \geq n_0}) 0 \leq cg(n) \leq f(n) \}\]

This is an asymptotic lower bound.

Theorem (notation relations) For any two functions \(f(n), g(n)\), we have

\[f(n) = \Theta(g(n)) \text{ iff } f(n) = O(g(n)), f(n) = \Omega(g(n))\]

asymptotics

2. 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)

3. 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)

4. Quantum Complexity

Definitions

  • BQP: decidable by quantum computer in polynomial time within ⅓ error probability.

Reference

  • [1] Introduction to Algorithm
  • [2] Introduction to the Theory of Computation