Articles · Computational complexity
What Is the P versus NP Problem?
The $1,000,000 question of whether every easily checked answer is also easy to find — open since 1971.
Some problems are hard to solve but easy to check. Given a proposed route through a hundred cities, verifying it’s under some target length is quick; finding the shortest route from scratch might take far longer. P versus NP asks whether that gap is real — whether every problem whose solution can be verified quickly (in polynomial time, the class NP) can also be solved quickly from scratch (the class P). Stephen Cook and Leonid Levin formulated the question independently in 1971.
Why almost everyone believes P ≠ NP
Thousands of problems — from scheduling to protein folding to circuit design — have been shown to be “NP-complete,” meaning a fast algorithm for any one of them would give a fast algorithm for all of them. Decades of trying and failing to find such an algorithm for even one NP-complete problem is the main evidence behind the near-universal (but unproven) belief that P ≠ NP.
What a “yes” would break
Modern public-key cryptography leans on problems believed to be hard to solve but is built on complexity assumptions weaker than P = NP specifically. Still, a constructive proof that P = NP would very likely make those hardness assumptions collapse too, since it would generally imply fast algorithms for the underlying hard problems themselves.
Why it’s here
P versus NP is one of the seven Millennium Prize Problems, each carrying a $1,000,000 award from the Clay Mathematics Institute for a correct proof either way. The Registry tracks it as an open record with its formal statement, distinct from the roundup of all seven, because the complexity-theory backstory is worth its own explanation.
Primary source
Reach people exploring this research with a visible sponsor panel for your organisation.
Sponsor this research Paid placement for an agreed term. Subject to independent review.