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