Is verification inherently easier than discovery? An interactive, math-free scrollytelling journey into the heart of computational complexity.
In 2000, the Clay Mathematics Institute chose seven monumental math problems and placed a $1,000,000 bounty on each. Today, only one has been solved. The most famous, widely discussed, and practically consequential of the remaining six is the P vs NP Problem.
Can the computer crack the secret code?
Checking every possible combination (Brute-Force) scales exponentially and takes a lot of time. But checking a combination that is already typed in (Verifying) happens instantly.
P vs NP asks: Is checking combinations mathematically, fundamentally easier than finding them? Or is there a clever algorithm that can find combinations just as easily as we check them?
Before modern microchips, Alan Turing designed a theoretical device: an infinitely long strip of paper tape divided into cells, a scanner head that reads/writes symbols, and a table of rules. This simple machine can compute anything a modern supercomputer can do. It defines the boundaries of computational power.
Below is the machine's program. When a rule matches the Current State and the Read Symbol on the tape, it triggers. Click on cells above to edit symbols manually.
| If State is | And Read is | Write Symbol | Move Head | Next State |
|---|
How do we define an "easy" problem? We measure how the number of steps grows as the input size (N) grows. If the steps scale as a polynomial equation (like N or N²), it belongs to class P (Polynomial Time). If it scales exponentially (like 2N), the computation explodes, becoming impossible to solve.
Like searching a list of N names. Easily manageable even with massive datasets.
Like comparing every item in a list with every other item (sorting). Feasible for ordinary computers.
Like cracking passwords. Scaling up N soon requires more time than the lifetime of the universe.
NP problems are ones where finding a solution is difficult (like finding a password), but verifying a solution is extremely fast and easy (polynomial time).
Try the 3-Coloring puzzle below. Can you color all 9 nodes (circles) in Red, Green, or Blue so that no two connected nodes share a color?
Solving is tedious, but verifying is instant.
💡 How to play: Click any node on the graph to cycle through colors: Grey (uncolored) ➔ Red ➔ Green ➔ Blue.
Are NP problems isolated riddles, or are they related? In 1971, computer scientists proved the **Cook-Levin Theorem**: Any NP problem can be translated (reduced) into a master logic problem called **SAT (Satisfiability)**. If we can find a fast algorithm to solve SAT, we can instantly solve every single problem in NP! Hover over the mini-graph below to see how nodes and edges translate directly into logical rules (clauses).
If someone solves P vs NP, they will prove either that P = NP or P ≠ NP. These two mathematical realities yield vastly different futures for our world.