Finishing a 1,000-piece jigsaw takes hours. Checking that someone else finished it takes seconds. Is that gap real, or have we just not found a clever enough method? That's P versus NP.

The dorm-room example
The Clay Mathematics Institute describes it like this. You have 400 students and room for only 100 in a dorm. The dean hands you a list of pairs who can't live together. Checking a proposed list of 100 is easy: just make sure no banned pair is on it. Finding such a list from scratch is another story: the number of ways to pick 100 of the 400 students is greater than the number of atoms in the known universe, so no computer could just try them all.
What P and NP mean

P is the set of problems a computer can solve quickly. NP is the set of problems where a proposed answer can be checked quickly. Clay's own shorthand: P is "easy to find," NP is "easy to check."
The big question: is every easy-to-check problem secretly easy to solve? If yes, P = NP. Most researchers suspect not, but nobody has proved it either way.
A $1 million question
Stephen Cook and Leonid Levin formulated the problem independently in 1971. In 2000 the Clay Institute picked it as one of seven Millennium Prize Problems, with $1 million for each solution. So far only one of the seven, the Poincaré conjecture, has been resolved.
FAQ
- What does NP stand for?
- Nondeterministic polynomial time. In plain terms: answers can be checked quickly.
- Has anyone solved P vs NP?
- No. It's still open, and the Clay prize is unclaimed.
- Why does it matter?
- It decides whether lots of hard scheduling, routing, and security problems have fast solutions.
Sources reviewed: 2026-11-20
References
- Clay Mathematics Institute. P vs NP. Official problem page: easy to check vs. easy to solve, the dormitory example, Cook and Levin 1971.
- Clay Mathematics Institute. The Millennium Prize Problems. Seven problems named in 2000, $1 million each; only the Poincaré conjecture solved.