Chapter 8 - NP Completeness

🏛️ Unit VIII: Complexity Classes

Design and Analysis of Algorithms (MIT121)

Second Semester — Master of Information Technology

⚖️ P vs NP 📜 Cook's Theorem 🔀 Reductions 🎯 Approximations

§ 8.1 & 8.2 — Introduction and Tractability

1. Introduction to NP-Completeness

Throughout this course, we studied algorithms that run efficiently — in polynomial time. But what about problems for which no efficient algorithm is known? NP-Completeness theory provides a rigorous framework for classifying such problems.

🎯

The Central Question (P vs NP): Is every problem whose solution can be quickly verified also quickly solvable? This is widely considered the most important open problem in computer science.

NP-complete problems are especially significant because:

• They appear naturally in many real-world optimization contexts.
• No polynomial-time algorithm is known for any of them.
• If any one NP-complete problem is solvable in polynomial time, then all NP problems can be solved in polynomial time.

2. Tractable vs Intractable Problems

Tractable Problem

A problem is tractable if it can be solved in polynomial time — i.e., an algorithm exists with worst-case running time O(nᵏ) for some constant k.

Intractable Problem

A problem is intractable if no polynomial-time algorithm is known (or provably cannot exist). These require exponential or worse time in the worst case.

Category	Example Problems	Best Known Time	Status
Tractable	Sorting, Shortest Path, MST, GCD	O(n log n) or better	✅ Efficient
Tractable	Matrix Multiplication, Flow	O(n²·³⁷) to O(n³)	✅ Polynomial
Unknown	SAT, TSP, Vertex Cover	O(2ⁿ) best known	❓ NP-complete
Intractable	Halting Problem, Tiling Problem	No algorithm exists	❌ Undecidable

§ 8.3 — Polynomial vs Super-Polynomial Time

3. Polynomial vs Super-Polynomial Time

Polynomial algorithms grow manageably; exponential algorithms become infeasible quickly

Growth	n=10	n=50	n=100	Class
O(n)	10	50	100	Poly ✅
O(n²)	100	2,500	10,000	Poly ✅
O(n³)	1,000	125,000	10⁶	Poly ✅
O(2ⁿ)	1,024	10¹⁵	10³⁰	Exponential ❌

§ 8.4 — Complexity Classes (P, NP, NP-Hard, NP-C)

4. Complexity Classes

P

Polynomial Time

Solvable in O(nᵏ) time by a deterministic algorithm. Ex: Sorting, BFS

NP

Non-deterministic Poly

Solutions can be verified in O(nᵏ) time. Ex: SAT, TSP

NP-H

NP-Hard

At least as hard as the hardest problems in NP. Ex: Halting

NPC

NP-Complete

Both in NP and NP-Hard. The hardest problems in NP. Ex: SAT, Clique

The Inclusion Diagram

Complexity class hierarchy assuming P ≠ NP

§ 8.5 & 8.6 — NP Problems & Reducibility

5. Important NP-Complete Problems

Problem	Description	Input	Decision Question
SAT	Boolean Satisfiability	Boolean formula φ	Is there an assignment making φ true?
Clique	Complete subgraph	Graph G, integer k	Does G have a clique of size k?
Vertex Cover	Cover all edges	Graph G, integer k	Is there a vertex cover of size ≤ k?
Subset Sum	Target sum from subset	Set S, target t	Is there a subset summing to t?
Hamiltonian Cycle	Visit all vertices once	Graph G	Does G have a Hamiltonian cycle?

6. Reducibility

Polynomial-Time Reduction (A ≤ₚ B)

Problem A is polynomial-time reducible to problem B if there exists a polynomial-time computable function f such that for every instance x: x is a YES instance of A ⟺ f(x) is a YES instance of B.

To prove a new problem C is NP-Complete:

1. Show C ∈ NP (verify a solution in poly-time).
2. Choose a known NP-Complete problem X (like 3-SAT).
3. Construct a reduction f: X → C in poly-time.
4. Prove x ∈ X ⟺ f(x) ∈ C.

§ 8.7 & 8.8 — Cook's Theorem & Proofs

7. Cook's Theorem (1971)

The Boolean Satisfiability Problem (SAT) is NP-Complete. That is, every problem in NP can be reduced to SAT in polynomial time. SAT was the first problem proven to be NP-Complete.

boolean logic

# Formula φ in CNF:
φ = (x₁ ∨ ¬x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂) ∧ (x₂ ∨ ¬x₃)
# Assignment: x₁=T, x₂=T, x₃=F evaluates to TRUE ✓

8. Proofs Series

• Clique ≤ₚ Vertex Cover: G has a clique of size k ⟺ G̅ (complement) has a vertex cover of size |V|−k.
• 3-SAT ≤ₚ Subset Sum: Encode variables/clauses as large integers where subsets sum to a specific target iff the formula is satisfiable.

SAT ≤ₚ 3-SAT 3-SAT ≤ₚ Clique Clique ≤ₚ Vertex Cover

§ 8.9 — Approximation Algorithms

9. Approximation Algorithms

Since NP-Complete problems lack polynomial-time exact solutions, we turn to approximation algorithms that run in polynomial time to find solutions provably close to optimal.

Approximation Ratio ρ(n)

An algorithm is a ρ(n)-approximation if the cost C satisfies max(C/C*, C*/C) ≤ ρ(n), where C* is optimal.

Vertex Cover (2-Approximation)

python

def approx_vertex_cover(edges):
    covered = set()
    remaining = edges.copy()
    while remaining:
        u, v = remaining.pop()       # pick any edge
        covered.add(u)
        covered.add(v)
        # remove all edges touching u or v
        remaining = {(a,b) for a,b in remaining
                     if a != u and a != v
                     and b != u and b != v}
    return covered

Problem	Approx Algorithm	Ratio	Time
Vertex Cover	Greedy matching	2	O(V+E)
Subset Sum	FPTAS with trimming	1+ε	O(n²log n/ε)
TSP (metric)	Christofides algorithm	1.5	O(n³)
Set Cover	Greedy	ln n + 1	O(n²)