Hard Problems

The travelling salesperson and P vs NP

An interactive lesson with 7 steps, about 6 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Brute-force route planning grows like $n!$, hopeless for large $n$.
• P: quickly solvable. NP: quickly checkable.
• Whether P = NP is a famous open problem with a $1 million prize.

Steps

1. Route planning
2. Twenty cities
3. P versus NP
4. Why it matters
5. NP-complete
6. Brute force versus the universe
7. Good enough