Coping with NP Completeness
It’s possible to solve NP complete problems!
- average case/worst case complexity: it’s possible to solve SAT for a lot of problems which solves the average case problems (“Heuristics vs. Algorithms”)
- special cases: 2SAT, subset sum, etc. can be solved in very special cases