Complexity Classes

P · NP · NP-complete · NP-hard

1:00

How computer scientists classify problems by inherent difficulty — P, NP, NP-complete, and NP-hard — and why the P vs NP question is the deepest open problem in the field.

By the end, you can

Define P, NP, NP-hard, and NP-complete and state how they relate to each other.
Explain the solve-vs-verify asymmetry and why it motivates the definition of NP.
Distinguish what NP does and does not mean (not "non-polynomial"; not necessarily slow).
State why P is a subset of NP.
Describe what a polynomial-time reduction is and what it proves about relative hardness.
Classify canonical problems (sorting, shortest path, SAT, Hamiltonian path, graph 3-colouring, knapsack) into their correct complexity classes.
Explain why solving any single NP-complete problem in polynomial time would imply P = NP.
State the Cook–Levin theorem and identify SAT as the first NP-complete problem.
Describe why the Halting Problem is NP-hard but not NP-complete.
List four practical strategies for coping with NP-complete problems in real applications.

Up next in Recursion, Paradigms & Algorithm Analysis