Phase 2: NP-Completeness

This phase introduces NP-Complete problems — the hardest problems inside NP, where if you solve one, you solve them all. We cover reductions, the Cook-Levin theorem, SAT, and a gallery of famous NP-Complete problems including the Traveling Salesman, Graph Coloring, Sudoku, and Minesweeper.

📄️ Reductions

If you can solve one problem, can you solve another? Reductions are the tool that lets us answer that question precisely — and they are the key to everything in Phase 2.

📄️ The Cook-Levin Theorem

In 1971, Stephen Cook proved that one specific problem sits at the top of the entire NP hierarchy — and that solving it would solve everything else. This is the result that launched the field of NP-Completeness.