Computational Complexity
Classify decision and optimization problems by their time/space requirements. Reductions transfer hardness across problems; NP-complete problems are universal for NP under polynomial-time reductions.
📘 Overview
Complexity theory studies the inherent difficulty of computational problems independent of specific hardware. It asks how resources like time and memory scale with input size and how problem classes relate.
📚 Fundamentals
- P: solvable in polynomial time
- NP: verifiable in polynomial time
- NP-complete: in NP and NP-hard
🛠️ Guides
How to Show NP-Completeness
- Prove the problem is in NP (certificates verifiable in poly-time).
- Choose a known NP-complete problem (e.g., 3-SAT).
- Construct a polynomial-time reduction to your problem.
- Argue correctness: yes-instances map to yes-instances and vice versa.
Common Reductions
- 3-SAT → Independent Set → Vertex Cover → Set Cover
- 3-SAT → Hamiltonian Cycle → TSP (decision)
🌍 Applications
- Crypto hardness: assumptions tied to worst/average-case complexity.
- Approximation: provable bounds when exact solutions are intractable.
- Heuristics: SAT solvers, local search, and branch-and-bound in practice.
🚀 Advanced
- PH, #P: counting and hierarchy above NP.
- PSPACE, EXPTIME: space/time beyond polynomial.
- Parameterized complexity: FPT and kernelization.
- Average-case: random instances vs worst-case.
🧪 Examples
- 3-SAT: clauses of three literals; canonical NP-complete.
- CLIQUE: size-k clique existence in a graph.
- SUBSET SUM: does any subset sum to target?
❓ Frequently Asked Questions
1) Is P = NP?
Open problem; resolving it would reshape computing and cryptography.
Open problem; resolving it would reshape computing and cryptography.
2) Why polynomial time?
Robust notion of efficient algorithms with closure properties.
Robust notion of efficient algorithms with closure properties.
3) Are all NP problems hard?
No. Some are in P (e.g., 2-SAT, bipartite matching).
No. Some are in P (e.g., 2-SAT, bipartite matching).
4) What is NP-hard vs NP-complete?
NP-hard may lie outside NP; NP-complete is both NP-hard and in NP.
NP-hard may lie outside NP; NP-complete is both NP-hard and in NP.
5) What about randomized algorithms?
Classes like BPP capture efficient randomized computation.
Classes like BPP capture efficient randomized computation.
6) Do reductions preserve approximability?
Gap-preserving reductions help transfer approximation hardness.
Gap-preserving reductions help transfer approximation hardness.
7) Are practical instances easy?
Many real-world instances are structured; solvers exploit this.
Many real-world instances are structured; solvers exploit this.
8) Does quantum break NP-complete?
No known quantum algorithm solves NP-complete problems in poly-time.
No known quantum algorithm solves NP-complete problems in poly-time.
9) Why parameterized complexity?
It isolates hard aspects into parameters for tractability.
It isolates hard aspects into parameters for tractability.
10) Best references?
Sipser’s “Introduction to the Theory of Computation”; Arora–Barak.
Sipser’s “Introduction to the Theory of Computation”; Arora–Barak.