P vs NP

What makes this fascinating

• A million-dollar question — Is every problem whose answer is easy to check also easy to solve? One of the seven Clay Millennium Prize Problems.

• Crack one, crack thousands — Scheduling, protein folding, code-breaking and more are all NP-complete — an efficient solution to one would solve them all.

• Almost everyone bets P ≠ NP — Most computer scientists believe finding is genuinely harder than checking, but after 50 years no one can prove it either way.

Frequently asked questions

Is P vs NP solved?

No. Whether P equals NP is the most famous open problem in computer science and a Clay Millennium Prize Problem. Most researchers expect P ≠ NP, but no proof in either direction exists.

What would it mean if P = NP?

It would mean every problem whose answer is easy to check is also easy to find. Much of modern cryptography would break, and hard search and optimization problems across science and logistics could become efficiently solvable.

Why is P vs NP so hard to prove?

Proving P ≠ NP means showing no fast algorithm can possibly exist for certain problems — a claim about every conceivable algorithm. Known proof techniques (relativization, natural proofs, algebrization) have each been shown unable to settle it.

More summits in Mathematics

• Riemann Hypothesis

  A 160-year-old pattern in the primes that no one can prove — math's most famous open problem.

• Navier–Stokes existence and smoothness

  We use the equations of fluid flow daily — yet can't prove their solutions never blow up.

• Birch and Swinnerton-Dyer conjecture

  A startling claim that a curve's whole-number solutions are encoded in a single function.

• The Collatz conjecture

  A rule a child can follow, an answer no mathematician can prove. Start anywhere — do you always reach 1?