Chapter 34 of 34

Complexity Classes: P, NP & NP-Complete

The last few chapters were about problems that no algorithm can solve. But being solvable is not enough in practice. Checking every possible timetable for a college with 60 courses, or every route for a delivery van with 40 stops, is "decidable", yet a brute-force program would run longer than the age of the universe. Complexity theory asks the next question: among the decidable problems, which can be solved efficiently?

This chapter introduces the classes P and NP, polynomial-time reductions, and NP-completeness, the idea behind the most famous open problem in computer science: does P equal NP?

P is the class of decision problems solvable by a deterministic algorithm in polynomial time. NP is the class of decision problems whose "yes" answers can be verified in polynomial time given a suitable certificate (equivalently, solvable by a nondeterministic TM in polynomial time). A problem is NP-complete if it is in NP and every problem in NP reduces to it in polynomial time.

We use the Turing machine model from Turing Machines and Variants of Turing Machines, and the idea of reductions from Reductions & Rice's Theorem, now with a time limit attached. All examples (the 3-SAT to CLIQUE reduction, the vertex cover graph, the subset-sum table) were checked with brute-force programs.


Measuring Time

Complexity is measured as a function of the input length n (the number of symbols needed to write the input down).

A deterministic TM M runs in time t(n) if, on every input of length n, it halts within t(n) steps. TIME(t(n)) is the class of languages decided by some O(t(n))-time deterministic TM. A nondeterministic TM runs in time t(n) if every branch of its computation halts within t(n) steps; NTIME(t(n)) is defined similarly.

We care about how the time grows. Compare a polynomial and an exponential algorithm at one billion steps per second:

n

n2 steps

n3 steps

2n steps

20

0.4 microseconds

8 microseconds

about 1 millisecond

50

2.5 microseconds

125 microseconds

about 13 days

100

10 microseconds

1 millisecond

about 4 × 1013 years

Doubling the input size multiplies a polynomial running time by a constant (8 for n3) but squares an exponential one. That is why the dividing line is drawn at polynomial time.

Why "polynomial" is a robust choice

  • A multi-tape TM running in time t(n) can be simulated by a single-tape TM in O(t(n)2) time. RAM machines and real computers are also polynomially related to TMs. So "polynomial time" means the same thing in every reasonable deterministic model.

  • Polynomials are closed under addition, multiplication and composition, so a polynomial algorithm that calls a polynomial subroutine polynomially many times is still polynomial.

  • In contrast, simulating a nondeterministic TM deterministically is only known to be possible with an exponential slowdown (2O(t(n))). Whether this blow-up is necessary is exactly the P vs NP question.

One caution: numbers are written in binary, so an input number N has about log2 N bits. An algorithm that runs in time proportional to N is exponential in the input length. We come back to this under "pseudo-polynomial" below.


The Class P

P = ⋃k TIME(nk): the decision problems solvable by a deterministic TM in polynomial time.

P is taken as the formal version of "efficiently solvable" (the Cobham–Edmonds thesis). Examples:

Problem (decision version)

Polynomial algorithm

PATH: is there a path from s to t in graph G?

BFS / DFS, O(V + E)

Are x and y relatively prime?

Euclid's algorithm, O(number of digits) iterations

Is w generated by CFG G? (fixed G)

CYK, O(n3)

Is there a path of weight ≤ k? (non-negative weights)

Dijkstra

Is there a spanning tree of weight ≤ k?

Kruskal / Prim

2-SAT: is a CNF formula with 2 literals per clause satisfiable?

Implication graph + strongly connected components, linear time

Is n prime?

AKS algorithm (2002), polynomial in the number of digits

Does a graph have a perfect matching? An Euler circuit?

Edmonds' blossom algorithm; degree check + connectivity


The Class NP

Many problems seem hard to solve but are easy to check. A Sudoku is hard to fill in, but if a friend hands you a completed grid, you can verify it in a minute. NP captures exactly this.

Definition 1: verifiers

A language L is in NP if there is a deterministic polynomial-time algorithm V (a verifier) and a polynomial p such that: w ∈ L if and only if there exists a certificate c with |c| ≤ p(|w|) for which V(w, c) accepts.

The certificate is the "proof" or "witness" of a yes-answer. Note the asymmetry: for a yes-instance some certificate convinces V; for a no-instance no certificate does.

Definition 2: nondeterministic machines

NP = ⋃k NTIME(nk): the languages decided by a nondeterministic TM in polynomial time.

The two definitions are equivalent. Given a verifier, a nondeterministic TM guesses the certificate (one branch per possible certificate) and runs V. Given a nondeterministic TM, the certificate is the sequence of choices made on an accepting branch. NP stands for "nondeterministic polynomial", not "non-polynomial".

Examples with their certificates

Problem

Question

Certificate

Verification

SAT

Is Boolean formula φ satisfiable?

A truth assignment

Evaluate φ

CLIQUE

Does G have a clique (all pairs adjacent) of size k?

The k vertices

Check all k(k−1)/2 pairs

VERTEX-COVER

Is there a set of ≤ k vertices touching every edge?

The set

Check every edge

HAM-CYCLE

Is there a cycle through every vertex exactly once?

The vertex order

Check it is a permutation and consecutive vertices are adjacent

SUBSET-SUM

Does some subset of the numbers add up to T?

The subset

Add it up

3-COLOR

Can the vertices be coloured with 3 colours, no edge monochrome?

The colouring

Check every edge

TSP (decision)

Is there a tour of total cost ≤ B?

The tour

Check it visits all cities and add the costs

P ⊆ NP

If a problem can be solved in polynomial time, the verifier can ignore the certificate and just solve it. So P ⊆ NP. Also, every NP problem can be solved in exponential time by trying all certificates (there are at most 2p(n) of them), so NP problems are always decidable: NP ⊆ EXPTIME.

The P vs NP question: is P = NP? In words, if a solution can be checked quickly, can it also be found quickly? Most researchers believe P ≠ NP, but no proof is known. It is one of the Clay Mathematics Institute's Millennium Prize Problems.


Polynomial-Time Reductions

This is the mapping reduction from Reductions & Rice's Theorem with one extra condition: the transformation must be fast.

A ≤p B (A is polynomial-time reducible to B) if there is a function f computable in polynomial time such that w ∈ A if and only if f(w) ∈ B.

Properties (same pattern as before, with "decidable" replaced by "in P"):

  • If A ≤p B and B ∈ P, then A ∈ P. (Compute f(w), whose size is polynomial in |w|, then run B's polynomial algorithm.)

  • If A ≤p B and B ∈ NP, then A ∈ NP.

  • ≤p is transitive.

  • Hardness flows forward: if A ≤p B and A is "hard", B is at least as hard.


NP-Hard and NP-Complete

B is NP-hard if every language A in NP satisfies A ≤p B. B is NP-complete if B is NP-hard and B ∈ NP.

NP-complete problems are the hardest problems in NP: each one encodes all of NP. This gives the key consequence:

If any NP-complete problem is in P, then P = NP. If P ≠ NP, then no NP-complete problem has a polynomial-time algorithm.

If P != NP (believed):                   If P = NP:

  +------------------------------+          +-----------------------+
  | NP                           |          | P = NP = NP-complete* |
  |   +------+      +----------+ |          +-----------------------+
  |   |  P   |      |   NPC    | |          (* except the trivial
  |   +------+      +----------+ |             languages empty and Σ*)
  +------------------------------+
            NP-hard = NPC and everything at least as hard
            (extends outside NP, e.g. the halting problem)

The Cook–Levin theorem

To use reductions we need a first NP-complete problem. Stephen Cook (1971) and, independently, Leonid Levin (1973) supplied it:

Cook–Levin Theorem. SAT (satisfiability of Boolean formulas) is NP-complete. The same holds for 3-SAT (CNF formulas with exactly 3 literals per clause).

Proof idea: take any NP language A, decided by a nondeterministic TM N in time nk. An accepting computation of N on w can be written as an nk × nk table (a "tableau") whose rows are the configurations. Build a formula with one Boolean variable for "cell (i, j) contains symbol s", and clauses saying: each cell holds exactly one symbol, the first row is the start configuration on w, every 2 × 3 window of the table follows N's transition rules, and an accept state appears. The formula has polynomial size and is satisfiable exactly when N has an accepting branch on w. So A ≤p SAT for every A in NP.

How to prove a new problem NP-complete

  1. Show B ∈ NP (give a certificate and a polynomial verifier).

  2. Pick a known NP-complete problem A and show A ≤p B: describe f, show it runs in polynomial time, and prove yes ↦ yes and no ↦ no.

Richard Karp (1972) used this to show 21 classic problems NP-complete; thousands are known today. The standard chain is:

SAT  -->  3-SAT  -->  CLIQUE  -->  INDEPENDENT-SET  <-->  VERTEX-COVER
            |
            +-->  3-COLOR
            +-->  SUBSET-SUM  -->  KNAPSACK, PARTITION
            +-->  HAM-CYCLE  -->  TSP (decision)
(arrow A --> B means A <=p B)

Worked Reduction: 3-SAT ≤p CLIQUE

Given a 3-CNF formula φ with m clauses, build a graph G and set k = m:

  • Vertices: one vertex for each literal occurrence (3m vertices, grouped in m triples).

  • Edges: join two vertices unless they are in the same clause or they are contradictory (x and ¬x).

Take

φ = (x1 ∨ x2 ∨ ¬x3) ∧ (¬x1 ∨ x2 ∨ x3) ∧ (x1 ∨ ¬x2 ∨ ¬x3)
        C1                  C2                 C3

G has 9 vertices. Between any two clauses there are 3 × 3 = 9 possible edges, 27 in total. Remove the contradictory pairs:

Clause pair

Contradictory pairs removed

Edges kept

C1 – C2

x1/¬x1, ¬x3/x3

7

C1 – C3

x2/¬x2

8

C2 – C3

¬x1/x1, x2/¬x2, x3/¬x3

6

Total

6

21

We ask for a clique of size k = 3. One is { x1 from C1, x2 from C2, x1 from C3 }: the three vertices are in different clauses and no two are contradictory, so all three edges exist. Setting x1 = 1 and x2 = 1 makes one literal in every clause true, so φ is satisfied (x3 can be either value). Our program counted 12 triangles of this kind and 5 satisfying assignments of φ, consistent with the equivalence.

Why it works:

  • φ satisfiable ⟹ clique of size m. In a satisfying assignment, pick one true literal from each clause. They are in different clauses, and two true literals can't be x and ¬x, so all pairs are joined.

  • Clique of size m ⟹ φ satisfiable. No two clique vertices share a clause, so the clique has exactly one vertex per clause. No two are contradictory, so we can make all of them true at once. Every clause then has a true literal.

  • Polynomial time: 3m vertices and at most (3m)2 edge checks.

CLIQUE is in NP (the certificate is the k vertices), so CLIQUE is NP-complete. We also tested the construction on 800 random 3-CNF formulas: "φ satisfiable" and "G has an m-clique" agreed every time.

Clique, independent set and vertex cover

These three are closely tied, so one NP-completeness proof gives all three:

  • S is a clique in G ⟺ S is an independent set (no two adjacent) in the complement graph Ḡ.

  • S is an independent set in G ⟺ V − S is a vertex cover (every edge has an endpoint in it). So G has an independent set of size k ⟺ G has a vertex cover of size n − k.

Example: vertices A, B, C, D, E with edges A–B, A–C, B–C, B–D, C–E, D–E (a triangle ABC attached to a path B–D–E–C).

Quantity

Value

One witness

Maximum independent set

2

{A, D}

Minimum vertex cover

3

{B, C, E} = V − {A, D}

Check

2 + 3 = 5 = |V|


Look-Alike Problems: Easy vs Hard

A tiny change in a problem can move it from P to NP-complete. These pairs are favourites in exams and interviews:

In P

NP-complete (decision version)

2-SAT

3-SAT, SAT

Euler circuit (use every edge once)

Hamiltonian cycle (visit every vertex once)

Shortest simple path (non-negative edge weights)

Longest simple path

2-colouring (bipartite test)

3-colouring

Minimum cut

Maximum cut

Minimum spanning tree

Steiner tree, TSP

Bipartite / general matching

3-dimensional matching

Linear programming

0-1 integer programming

Vertex cover in a bipartite graph (König's theorem)

Vertex cover in a general graph


Pseudo-Polynomial Algorithms

SUBSET-SUM is NP-complete, yet there is a well-known dynamic program. Is that a contradiction? No. Let D[i][t] be true if some subset of the first i numbers sums to t. For the set {3, 5, 8, 11} and target T = 16:

t =        0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
{}         T  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
{3}        T  .  .  T  .  .  .  .  .  .  .  .  .  .  .  .  .
{3,5}      T  .  .  T  .  T  .  .  T  .  .  .  .  .  .  .  .
{3,5,8}    T  .  .  T  .  T  .  .  T  .  .  T  .  T  .  .  T
{3,5,8,11} T  .  .  T  .  T  .  .  T  .  .  T  .  T  T  .  T

D[4][16] is true (16 = 5 + 11 = 3 + 5 + 8), while D[4][12] is false (no subset sums to 12). The table has (n + 1)(T + 1) entries, so the time is O(nT). But T is written with only about log2 T bits, so O(nT) is exponential in the input length. With 100 numbers of 60 bits each, T can be around 260. Such an algorithm is called pseudo-polynomial; problems like SUBSET-SUM and 0/1 KNAPSACK that have one are called weakly NP-complete. Problems such as 3-SAT, CLIQUE and HAM-CYCLE, which stay hard even when all numbers are small, are strongly NP-complete.


NP-Hard Problems Outside NP, and co-NP

NP-hard does not mean "in NP"

  • Optimisation versions ("find the shortest tour") are not decision problems at all, so they are not in NP, but they are NP-hard: solving them answers the decision version.

  • The halting problem is NP-hard: map a formula φ to a program that tries all assignments and halts if one satisfies φ, otherwise loops. This is a polynomial-time reduction SAT ≤p HALT. But HALT is undecidable, so it is certainly not in NP. NP-hard problems can be much harder than NP.

co-NP

co-NP is the class of complements of NP languages: problems whose "no" answers have short certificates. Example: UNSAT ("is φ unsatisfiable?") and TAUTOLOGY ("is φ true under every assignment?"). A short proof that φ is satisfiable is easy (an assignment), but no short proof of unsatisfiability is known.

  • P ⊆ NP ∩ co-NP (P is closed under complement).

  • If P = NP then NP = co-NP. It is believed that NP ≠ co-NP.

  • The decision version of integer factoring ("does N have a factor ≤ k?") is in NP ∩ co-NP, but no polynomial algorithm is known; it is not believed to be NP-complete.

NP-intermediate problems

Ladner's theorem (1975): if P ≠ NP, there are problems in NP that are neither in P nor NP-complete. Graph isomorphism and factoring are the usual suspects, but nobody has proved either is NP-intermediate (that would prove P ≠ NP).


The Bigger Picture

P  ⊆  NP  ⊆  PSPACE  =  NPSPACE  ⊆  EXPTIME  ⊆ ... ⊆  Decidable  ⊊  RE
                           (Savitch)

Known for sure:    P ≠ EXPTIME        (time hierarchy theorem)
                   Decidable ≠ RE     (halting problem)
Open:              P vs NP,  NP vs PSPACE,  PSPACE vs EXPTIME
  • PSPACE is the class of problems solvable with polynomial memory (time may be exponential). Savitch's theorem shows nondeterminism does not help much for space: NPSPACE = PSPACE. TQBF (true quantified Boolean formulas) and deciding winners in generalised games are PSPACE-complete.

  • Since P ≠ EXPTIME, at least one of the inclusions P ⊆ NP ⊆ PSPACE ⊆ EXPTIME is strict, but we do not know which.

Class

Meaning

Typical complete problem

P

Solvable in polynomial time

(Circuit value problem, under log-space reductions)

NP

Yes-answers verifiable in polynomial time

SAT, 3-SAT, CLIQUE, HAM-CYCLE

co-NP

No-answers verifiable in polynomial time

TAUTOLOGY, UNSAT

PSPACE

Solvable with polynomial memory

TQBF

EXPTIME

Solvable in 2poly(n) time

Generalised chess / checkers on n × n boards


Common Mistakes

  • "NP means non-polynomial." It means nondeterministic polynomial. Every problem in P is also in NP.

  • "NP-complete problems cannot be solved." They are all decidable, by exhaustive search in exponential time, and often solvable quickly in practice (SAT solvers handle millions of variables on real inputs). The question is about worst-case polynomial time.

  • Reducing in the wrong direction. To show B is NP-hard, reduce a known NP-complete problem to B (3-SAT ≤p B). Showing B ≤p 3-SAT only proves B ∈ NP.

  • "NP-hard implies NP." No: the halting problem is NP-hard but undecidable.

  • Forgetting the "in NP" part. NP-complete = NP-hard + in NP. Both must be shown.

  • Calling O(nT) or O(nW) polynomial. These are pseudo-polynomial: polynomial in the value of the numbers, exponential in their bit length.

  • Thinking 2-SAT is NP-complete. 2-SAT is in P; the jump happens at 3 literals per clause.

  • Confusing the Hamiltonian and Euler problems. Euler (edges) is easy; Hamiltonian (vertices) is NP-complete.


GATE and Interview Questions

Q1. Problem X is NP-complete. Problem Y is in NP and X ≤p Y. What can you conclude about Y?

Y is NP-complete. Every NP problem reduces to X, and X reduces to Y, so by transitivity every NP problem reduces to Y (Y is NP-hard). With Y ∈ NP, Y is NP-complete.

Q2. Problem A is in P and B ≤p A. Problem C is NP-complete and C ≤p D. Which follow? (i) B ∈ P (ii) D is NP-hard (iii) D ∈ NP (iv) A is NP-hard.

(i) and (ii). (i): reductions transfer membership in P from A down to B. (ii): hardness transfers from C up to D. (iii) is not guaranteed (D might be undecidable, like HALT). (iv) does not follow; it would imply P = NP.

Q3. Which of these problems are in P: 2-SAT, 3-SAT, Euler circuit, Hamiltonian cycle, primality, shortest path, longest path?

2-SAT, Euler circuit, primality (AKS) and shortest path. 3-SAT, Hamiltonian cycle and longest path (decision versions) are NP-complete.

Q4. If someone finds a polynomial-time algorithm for 3-COLOR, what happens?

3-COLOR is NP-complete, so every NP problem would be solvable in polynomial time: P = NP. Consequently NP = co-NP as well, and problems like SAT, CLIQUE and TSP (decision) would all be in P.

Q5. 0/1 knapsack has an O(nW) dynamic-programming solution. Why is it still NP-complete (decision version)?

W is given in binary using about log W bits, so O(nW) is exponential in the input length. It is a pseudo-polynomial algorithm, which does not put the problem in P. (Knapsack is weakly NP-complete.)

Q6. Is the halting problem NP-complete?

No. It is NP-hard (SAT ≤p HALT) but not in NP, since it is undecidable. NP-complete problems must be in NP.

Q7. A graph has 10 vertices and its maximum independent set has size 4. What is the size of its minimum vertex cover?

6. The complement of an independent set is a vertex cover, and vice versa, so min VC = n − max IS = 10 − 4.

Q8. Interview: your task looks NP-complete. What do you do in practice?

Check whether your inputs are a special case in P (small k, trees, bipartite graphs, 2 literals per clause). Otherwise use an exact solver that is fast on typical inputs (SAT/ILP solvers, branch and bound), an approximation algorithm with a guarantee (e.g. 2-approximation for vertex cover), a pseudo-polynomial DP if the numbers are small, or heuristics such as local search.


Summary

  • P: decision problems solvable in polynomial time by a deterministic TM; the formal meaning of "efficient".

  • NP: yes-answers have polynomial-size certificates checkable in polynomial time; equivalently, nondeterministic polynomial time. P ⊆ NP ⊆ PSPACE ⊆ EXPTIME.

  • A ≤p B: a polynomial-time mapping reduction. B ∈ P ⟹ A ∈ P; A hard ⟹ B hard.

  • NP-hard: every NP problem reduces to it. NP-complete: NP-hard and in NP.

  • Cook–Levin: SAT (and 3-SAT) is NP-complete. Other problems are shown NP-complete by reductions such as 3-SAT ≤p CLIQUE.

  • If any NP-complete problem is in P, then P = NP. Whether P = NP is open.

  • Watch the look-alikes (2-SAT vs 3-SAT, Euler vs Hamiltonian, shortest vs longest path) and pseudo-polynomial algorithms (subset sum, knapsack).

Computability asks what can be solved at all; complexity asks what can be solved in a reasonable time. NP-complete problems are the ones where checking an answer is easy but finding one seems hard, and solving any one of them fast would solve them all.