Skip to content
The Lumenary
Advanced undergraduateComputationPlanned

Computational complexity

Time and space complexity classes, P and NP, polynomial-time reductions, NP-completeness and the Cook–Levin theorem, and the status of the P versus NP problem.

math.comp.complexity-theory

Show everything needed to reach this topic

The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.

Builds on

ComputabilityAlgorithm design and analysis

Required prerequisites, all the way down: 25

You will learn to

  • Define P and NP and place standard problems in them.
  • Prove NP-completeness of problems such as 3-SAT, vertex cover or graph 3-colouring by reductions.
  • Explain what is known and unknown about P versus NP, and why cryptography relies on unproved hardness assumptions.

Definition

  • P is the class of decision problems solvable in polynomial time by a deterministic Turing machine.
  • NP is the class of decision problems whose yes-instances have certificates that can be verified in polynomial time.
  • A problem is NP-complete if it is in NP and every problem in NP reduces to it in polynomial time.

Theorem

  • Cook–Levin: Boolean satisfiability (SAT) is NP-complete.
  • P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, and P ≠ EXPTIME by the time hierarchy theorem.
  • Whether P = NP is open; it is one of the Clay Mathematics Institute's Millennium Prize Problems.

Common misconceptions

  • Thinking NP stands for 'not polynomial'; it stands for nondeterministic polynomial time.
  • Believing NP-complete problems cannot be solved in practice; many large instances are solved routinely.

Optional discoveries

Learning pathways

Further reading

  • Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (2009)
  • Michael Sipser, Introduction to the Theory of Computation (1996)