Algorithms & EmergenceComputational Complexity

Easy to Check, Hard to Solve

Checking a sudoku takes seconds; solving one can take ages

Spotting a mistake in a finished sudoku takes seconds. So why can filling in the same grid take you an hour?

You'll find out

  • How few steps checking really takes
  • Why solving needs so many guesses
  • The $2 million puzzle nobody finished

Why it matters

Timetables, deliveries and puzzles all share this gap, and it sets up one of math's biggest open questions.

About 3 min6 interactive slides · 5 questionsLesson 656 · Zone 73

Play this lesson

Free to play in your browser or on iPhone

More in this zone

  1. 649NumbersLogarithmsWhy earthquakes and sound use strange scales
  2. 650Biomedical EngineeringThe Mind-Controlled HandMuscle signals can move an artificial hand
  3. 651TopologyThe Klein BottleA bottle with no inside that can't exist in our world
  4. 652Probability FoundationsBertrand's ParadoxOne question about a random line has three correct answers
  5. 653Software HistoryLinux Was ‘Just a Hobby’A student's side project now runs most of the world's servers
  6. 654Content ProvenanceWatermarking AIGenerated media can carry hidden clues about where it came from
  7. 655Space ExplorationThe Pale Blue DotEarth seen from 6 billion kilometers is a speck in a sunbeam
  8. 657Computational ComplexityP vs NPA million-dollar question about whether finding is harder than checking