한
Puzzle listView on map

One great problem, three kinds of immersion

From a story to your own conjecture

Problem stories open curiosity. The problem workshop is the next place, where curiosity becomes a testable idea.

  1. 1 · DiscoverYou are hereMeet the questionLearn when it appeared and why it still holds people’s attention.
  2. 2 · ChallengeTest one caseMake your first observation in five minutes with a drawing, calculation, or colors.
  3. 3 · DevelopBuild on ideasPublish an observation and grow it through comparisons, conjectures, and counterexamples.
Open1971

P vs NP — Is Fast Verification the Same as Fast Search?

If a proposed solution to a decision problem can be verified in polynomial time, can a solution also be found in polynomial time? Familiar puzzles and routing tasks lead to a central question in complexity theory.

Challenge passport
First posed
1971
Time it held mathematicians
55 years open · as of 2026
Starting level
Explore

Learn the rule, then go farther with calculation or a small program.

The starting level measures how easily you can understand and test small cases. It is not the difficulty of a complete proof.

Jump to your first five minutes

Clay Mathematics Institute — $1 million (Millennium Problem)

See the puzzle visually

125 cities(n−1)!/2 routes181k10 cities(n−1)!/2 routes60800.0T20 cities(n−1)!/2 routes4.7×10^155100 cities(n−1)!/2 routeslog

The Traveling Salesperson Problem already has more routes than atoms in the universe at 100 cities. If P=NP, it has a polynomial-time solution; so far we only know the exponential explosion.

Problem statement

P = problems solvable in polynomial time. NP = problems whose solutions are verifiable in polynomial time. Does P = NP? Formalized by Stephen Cook in 1971.

The story of this puzzle

Checking a completed generalized Sudoku is fast; finding a completion may be much harder. Here “fast” means polynomial in input size, not a few seconds on one instance. If P=NP, every NP-complete decision problem has a polynomial-time algorithm, with major consequences for optimization and cryptographic assumptions; the polynomial might still be impractical. Barrier results such as relativization, natural proofs, and algebrization show why familiar techniques may not settle the question, but they do not prove independence.

Try it yourself

Mini challenge

For symmetric distances, fixing the start and identifying reverse tours leaves (n−1)!/2 distinct tours: 12 for five cities and 181,440 for ten. Solving one 100-city instance quickly does not prove P=NP; it would take a general exact polynomial-time algorithm for decision TSP together with a complexity proof.

Beyond MathVoyage

Loading…