NP-Completeness
P vs NP, polynomial reductions, NP-hard, NP-complete problems — complete GATE CS coverage.
Last updated: April 2026 | GATE CS 2024–2026 syllabus
Key Takeaways
- P: decidable in polynomial time. NP: verifiable in polynomial time.
- P ⊆ NP. Whether P = NP is the greatest open problem in computer science.
- NP-hard: every NP problem reduces to it (may not be in NP itself).
- NP-complete: in NP AND NP-hard — the hardest problems in NP.
- To prove NP-complete: (1) show problem in NP + (2) reduce known NP-complete problem to it.
- SAT is the first NP-complete problem (Cook, 1971). 3-SAT reduces from SAT.
- If any NP-complete problem is in P, then P = NP (all NP problems collapse to P).
1. Complexity Classes
Examples: sorting, shortest paths, MST, matrix multiplication.
NP (Nondeterministic Polynomial): Problems where a given solution can be verified in polynomial time.
Equivalently: solvable in polynomial time on a nondeterministic Turing machine.
Examples: TSP (verify tour length ≤ k in O(n)), graph colouring, SAT.
co-NP: Problems whose complement is in NP. (Verify NO-instances in poly time.)
Example: Tautology (is every truth assignment satisfying?)
NP-hard: Every problem in NP polynomial-time reduces to it. May not be in NP.
NP-complete: In NP AND NP-hard.
Relationships: P ⊆ NP, P ⊆ co-NP, NP-complete ⊆ NP ⊆ NP-hard.
| Class | Solvable in poly time? | Verifiable in poly time? |
|---|---|---|
| P | Yes | Yes |
| NP | Unknown | Yes |
| NP-complete | Unknown (would imply P=NP) | Yes |
| NP-hard | No (unless P=NP) | Not necessarily |
2. Polynomial Reductions
Informal: if we can solve B, we can solve A (A is no harder than B).
Reduction procedure:
Transform any instance x of A to instance f(x) of B in polynomial time, such that:
x is YES-instance of A ⇔ f(x) is YES-instance of B.
Key properties:
If A ≤p B and B ∈ P ⇒ A ∈ P
If A ≤p B and A is NP-hard ⇒ B is NP-hard
Reduction direction: reduce FROM known hard problem TO new problem (to prove new is hard).
3. SAT and Cook’s Theorem
Input: Boolean formula φ with variables x1,…,xn.
Question: Does there exist a truth assignment satisfying φ?
Cook’s theorem (1971): SAT is NP-complete.
Every NP problem can be reduced to SAT in polynomial time.
3-SAT: SAT restricted to clauses with exactly 3 literals.
3-SAT is NP-complete. SAT ≤p 3-SAT (general SAT reduces to 3-SAT).
2-SAT: Each clause has ≤2 literals. 2-SAT is in P (O(V+E) via SCC on implication graph).
4. Classic NP-Complete Problems
| Problem | Description | Reduces From |
|---|---|---|
| SAT | Satisfying assignment for Boolean formula | First (Cook’s theorem) |
| 3-SAT | SAT with 3-literal clauses | SAT |
| Clique | Graph has clique of size k | 3-SAT |
| Independent Set | Graph has independent set of size k | Clique |
| Vertex Cover | k vertices cover all edges | Independent Set |
| Graph Colouring (k≥3) | Colour with k colours, no adjacent same | 3-SAT |
| Hamiltonian Cycle | Cycle visiting all vertices exactly once | 3-SAT or Clique |
| TSP (decision) | Tour of length ≤k exists | Hamiltonian Cycle |
| Subset Sum | Subset with sum exactly T | 3-SAT |
| 0-1 Knapsack (decision) | Value ≥K, weight ≤W achievable | Subset Sum |
| Set Cover | k sets covering all elements | Vertex Cover |
| Partition | Split set into two equal-sum halves | Subset Sum |
SAT → 3-SAT → Clique → Independent Set ↔ Vertex Cover
3-SAT → Hamiltonian Cycle → TSP
3-SAT → Subset Sum → Knapsack
Vertex Cover → Set Cover
5. NP-Hard (but not NP-Complete)
Optimisation versions:
TSP optimisation (find shortest tour): NP-hard (not in NP — verifying optimality is hard).
Knapsack optimisation: NP-hard.
MAX-SAT (maximise satisfied clauses): NP-hard.
Beyond NP:
Halting problem: undecidable (not even in NP-hard in the classical sense).
PSPACE-hard problems: harder than NP-complete.
6. Dealing with NP-Hard Problems
TSP (metric): 2-approximation via MST doubling.
Vertex Cover: 2-approximation via maximal matching.
Set Cover: O(log n)-approximation.
FPT (Fixed-Parameter Tractable): O(f(k) × nc) where k = parameter.
Vertex cover: O(2k × kn) — FPT in k.
Pseudo-polynomial: O(nW) for Knapsack — polynomial if W is bounded.
Special cases: Some NP-hard problems are poly-time for restricted inputs (e.g., TSP on trees is O(n)).
7. GATE Examples
(A) Finding MST (B) Finding shortest path (C) Graph 3-colouring (D) Topological sort
Answer: (C) Graph 3-colouring. Options A, B, D are all polynomial-time solvable.
If B ∈ P and A ≤p B, then A ∈ P. We can solve A using the polynomial reduction to B and B’s poly-time algorithm.
Yes (in general). But for small fixed k, it is FPT. The decision version “does graph G have vertex cover of size ≤k” is NP-complete in general (varies with k as input), but poly-time for fixed k.
8. Common Mistakes
- Confusing NP with “non-polynomial”: NP stands for Nondeterministic Polynomial — it means verifiable in polynomial time, NOT “non-polynomial time”.
- NP-hard requires no poly-time solution ONLY if P≠NP: NP-hardness means “no poly algorithm known” — it’s an assumption, not a proof (since P vs NP is unsolved).
- Reduction direction: To prove X is NP-hard, reduce FROM a known NP-hard problem TO X. Not from X to something else.
- TSP optimisation vs decision: The decision version (tour ≤k?) is NP-complete. The optimisation version (find minimum tour) is NP-hard (verifying optimality is hard).
- 2-SAT is in P: 2-SAT is NOT NP-complete — it’s solvable in O(V+E) via implication graph and SCC. Only 3-SAT (and larger) is NP-complete.
9. FAQ
- What is the difference between P, NP, NP-hard, and NP-complete?
- P: solvable in polynomial time. NP: verifiable in polynomial time (includes P). NP-hard: every NP problem reduces to it in polynomial time — these are at least as hard as the hardest NP problems. NP-complete: in NP AND NP-hard — they are both verifiable and the hardest in NP.
- How do you show a problem is NP-complete?
- Two steps: (1) Show the problem is in NP by giving a polynomial-time verifier (certificate checker). (2) Show it is NP-hard by taking a known NP-complete problem and constructing a polynomial-time reduction from that problem to your problem.
- What is Cook’s theorem?
- Cook’s theorem (1971) proves that SAT (Boolean Satisfiability) is NP-complete — it was the first problem proven NP-complete. The proof shows every NP problem can be translated into a SAT instance in polynomial time via a Turing machine simulation.
- Is 0-1 Knapsack NP-complete?
- The decision version (does there exist a selection with value ≥K and weight ≤W?) is NP-complete. The DP solution runs in O(nW) — pseudo-polynomial, not polynomial, because W can require Ω(log W) bits to represent, making the actual input size O(n log W), not O(nW).