05
Computational Complexity
Chapter 5 • Advanced
60 min
Computational Complexity
Computational Complexity studies resource requirements of problems.
Complexity Classes
P (Polynomial Time)
P: Problems solvable in polynomial time by deterministic TM.
Examples:
- Sorting
- Shortest path
- Matrix multiplication
NP (Nondeterministic Polynomial Time)
NP: Problems solvable in polynomial time by non-deterministic TM.
Equivalently: Problems with polynomial-time verifier.
Examples:
- SAT (Boolean satisfiability)
- Hamiltonian path
- Clique
NP-Complete
NP-Complete: Problems in NP to which every NP problem reduces.
Properties:
- In NP
- All NP problems reduce to it
Examples:
- SAT
- 3-SAT
- Clique
- Vertex Cover
- Hamiltonian Cycle
NP-Hard
NP-Hard: Problems to which all NP problems reduce.
May not be in NP.
Examples:
- Halting problem
- Optimization versions of NP-complete
P vs NP Problem
Open Question: Is P = NP?
If P = NP:
- Many hard problems become easy
- Cryptography breaks
If P ≠ NP:
- Some problems inherently hard
- Current understanding
Reduction
Polynomial-Time Reduction:
- Problem A reduces to B in polynomial time
- If B ∈ P, then A ∈ P
- If A is NP-hard, then B is NP-hard
Use: Prove NP-completeness.
Cook-Levin Theorem
Cook-Levin Theorem: SAT is NP-complete.
Proof:
- SAT ∈ NP (verifiable)
- Every NP problem reduces to SAT
- Therefore, SAT is NP-complete
Significance: First NP-complete problem.
Common NP-Complete Problems
- SAT: Boolean satisfiability
- 3-SAT: 3-CNF satisfiability
- Clique: Find clique of size k
- Vertex Cover: Find vertex cover of size k
- Hamiltonian Cycle: Find Hamiltonian cycle
- Traveling Salesman: TSP decision problem
- Subset Sum: Find subset summing to target
GATE CS Important Points
- P vs NP: Understand difference
- NP-Complete: Know examples
- Reduction: Use for NP-completeness proofs
- Cook-Levin: Understand significance
- Complexity Classes: Know hierarchy
Practice Tips
- Identify Complexity: Classify problems
- NP-Completeness: Prove using reduction
- Common Problems: Know NP-complete problems
- Reduction: Practice polynomial-time reductions
- Previous Year Questions: Solve GATE complexity questions