← 🧮 P, NP & NP-Completeness
Subtopic 1 of 3

5.1P, NP, NP-hard and NP-complete

The idea

P problems can be solved fast; NP problems can have their answers checked fast. NP-complete problems are the hardest ones in NP.

Think of it like this: A jigsaw puzzle: hard to solve, but trivial to check that a finished picture is right.

Why it exists

Four definitions and the relations between them make up most NP questions.

How it works

  1. P: polynomial-time solvable. P ⊆ NP.
  2. NP: a certificate can be verified in polynomial time.
  3. NP-hard: every NP problem reduces to it (it may lie outside NP).
  4. NP-complete = NP ∩ NP-hard.

Worked example: Boolean satisfiability

Given an assignment you check all clauses in one pass: SAT is in NP. It is also NP-hard (Cook-Levin), so it is NP-complete.

Now play with it

  • →Flip the variable buttons and watch the clause check.
  • →Compare the 2⁴ search space with the one-pass check.

3-SAT: (x1 ∨ ¬x2 ∨ x3) ∧ (¬x1 ∨ x2 ∨ x4) ∧ (x2 ∨ ¬x3 ∨ ¬x4) ∧ (¬x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ x3 ∨ x4). Flip the variables to propose a certificate.

clause12345
satisfied?✓✓✗✓✓
Verdictcertificate rejected
Checking costone pass over the clauses: polynomial
Brute-force search space2^4 = 16 assignments (2^n in general); 7 satisfy the formula

NP means "easy to verify": given a certificate, a polynomial check settles it. Nobody knows whether finding one is also easy (P = NP?). With n variables the search space is 2ⁿ, the check is still a single pass.

ClassMeaningExamples
Psolvable in polynomial timesorting, shortest path, MST, 2-SAT, bipartite matching
NPa certificate is checkable in polynomial timeeverything in P, plus SAT, Clique, Hamiltonian cycle
NP-hardevery NP problem reduces to itSAT, TSP, the halting problem (not in NP)
NP-completeNP and NP-hardSAT, 3-SAT, Clique, Vertex cover, 3-colouring, Subset sum

If P ≠ NP: P and NP-complete are disjoint. If any NP-complete problem is in P, then P = NP.

Check yourself

If an NP-complete problem is solved in polynomial time, then

Remember: P ⊆ NP; NP-complete = in NP and NP-hard; certificate checking is the NP test.
Exam notes (the dense version)

P: solvable in polynomial time. NP: a proposed solution (certificate) can be verified in polynomial time. P ⊆ NP; whether P = NP is open. NP-hard: at least as hard as every problem in NP (need not be in NP). NP-complete: in NP and NP-hard. If any NP-complete problem is in P then P = NP.