P versus NP

Let $P$ be the class of decision problems decidable by a deterministic Turing machine in polynomial time, and let $NP$ be the class decidable by a nondeterministic Turing machine in polynomial time.

Is $P = NP$ ?

Download

Abstract

The question asks whether efficient verification always implies efficient computation. A proof of $P=NP$ would give polynomial-time algorithms for every NP-complete problem; a proof of $P\ne NP$ would establish a fundamental limitation of efficient algorithms.

Any proposed resolution must use a standard computational model and address uniform polynomial time, not merely individual instances or restricted algorithms.

Background and progress

1971: Stephen Cook formalized NP-completeness through the satisfiability problem.
1972: Richard Karp showed that many central combinatorial problems are NP-complete.
2000: The Clay Mathematics Institute selected P versus NP as a Millennium Prize Problem.

Reference papers

The P versus NP ProblemStephen CookClay Mathematics Institute · 2000 ↗