P vs NP
Is finding an answer as easy as checking it?
01 / The question
A proposed answer can sometimes be checked quickly even when finding one seems difficult. P vs NP asks whether every decision problem whose yes-answers have efficiently checkable certificates can also be solved in polynomial time.
02 / Why it is hard
Exhaustive search being slow is not a proof that every possible algorithm is slow. The challenge is to reason about all algorithms, not just ones we already know.
03 / Progress & scope
Clay lists P vs NP as unsolved. Results about particular algorithms or restricted models do not by themselves settle this full question.
Try an experiment
Make an abstract question tangible
Try a small subset-sum instance. Enumerating its subsets shows one search method, not a lower bound for every method.
Select numbers to try to reach the target.
Selected sum: 0 / 41
10 values have 1,024 subsets. Checking a selected answer takes at most 10 additions.
This compares one enumeration method with certificate checking. It does not prove P ≠ NP or rule out faster algorithms.
Sources & further reading
Clay Mathematics InstituteSources last checked 2026-10-20. Status reflects an editorial review on that date, not continuous live monitoring.