Computational Complexity

When to use

• Classifying a problem as P, NP-complete, or NP-hard before choosing an algorithm
• Proving a problem is NP-complete via polynomial-time reduction
• Selecting between exact, approximation, FPT, or heuristic approaches
• Designing approximation algorithms with provable guarantees (PTAS, FPTAS)
• Deciding when randomized algorithms (Las Vegas vs Monte Carlo) are appropriate
• Identifying when a parameter makes an otherwise hard problem tractable (FPT)

Core principles

1. Classify before solving — knowing a problem is NP-hard changes the entire strategy
2. Reduction direction matters — reduce FROM a known hard problem TO yours to prove hardness
3. Approximation ratio is a guarantee, not a hope — an unproven heuristic is not an approximation algorithm
4. Small parameter = FPT opportunity — exponential in k is fine when k ≤ 20
5. Amplify randomized correctness — repeat Monte Carlo k times to push error below 2^(-k)