P vs NP problem

P vs NP problem
Name	P vs NP problem
Field	Mathematics; Computer science
Discovered	1971
Contributors	Stephen Cook, Leonid Levin, Richard Karp, Donald Knuth, Alan Turing
Status	Open problem
Prize	Clay Mathematics Institute Millennium Prize

P vs NP problem The P vs NP problem asks whether every decision problem whose solutions can be verified quickly by a Turing machine can also be solved quickly by a Turing machine. Formulated in the early 1970s and crystallized by Stephen Cook and Leonid Levin, the question sits at the intersection of Mathematics, Computer science, and theoretical Cryptography and is one of the seven Millennium Prize Problems designated by the Clay Mathematics Institute.

Overview

P and NP are central complexity classes defined using deterministic and nondeterministic Turing machine models. The class P captures decision problems solvable in polynomial time on a deterministic Turing machine, while NP captures those decidable in polynomial time on a nondeterministic Turing machine or verifiable by a deterministic Turing machine given a witness. Major milestones include Stephen Cook's 1971 paper, Richard Karp's 1972 list of 21 NP-complete problems, and subsequent developments by Leonid Levin, Michael Rabin, Gary Miller, and Avi Wigderson. The problem influences research at institutions such as Massachusetts Institute of Technology, Stanford University, Princeton University, and corporations like IBM and Microsoft Research.

Formal definitions

P is the set of languages decidable by a deterministic Turing machine in time O(n^k) for some fixed k. NP is the set of languages for which membership proofs (witnesses) can be verified by a deterministic Turing machine in polynomial time, equivalently languages decidable by a nondeterministic Turing machine in polynomial time. Reductions central to NP-completeness use polynomial-time many-one reductions introduced by Stephen Cook and popularized by Richard Karp. The Cook–Levin theorem establishes Boolean satisfiability problem as NP-complete, connecting to problems studied by C. E. Shannon and frameworks used in Alonzo Church's lambda calculus and Alan Turing's decision problems. Completeness and hardness notions are formalized alongside complexity measures from Claude Shannon information theory and analysis techniques advanced by Donald Knuth.

Known results and partial progress

Several separations and collapses among classes related to P and NP are known. Time hierarchy theorems by Jurassic? — correction: the deterministic time hierarchy due to Jurgen Hartmanis and Richard Stearns—show proper containment for larger time bounds. Relativization results by Baker, Gill, and Solovay demonstrate oracles relative to which P=NP and others where P≠NP, while natural proofs barriers were identified by Alexander Razborov and Steven Rudich. Interactive proof characterizations such as IP=PSPACE were proved by Adrian Fortnow, László Babai, and Shafi Goldwasser's contemporaries; the PCP theorem arose through work involving Irit Dinur and others, tightening hardness of approximation results linked to Subhash Khot's Unique Games Conjecture. Circuit lower bounds results by researchers like Valiant and barriers like relativization, natural proofs, and algebrization by Aaronson and Wigderson constrain proof strategies. Many NP-intermediate candidate problems trace to work by Leonid Levin and structural complexity results by László Babai and Sanjeev Arora.

Importance and implications

If P=NP, efficient algorithms would exist for myriad NP-complete problems such as Boolean satisfiability problem, Hamiltonian path problem, Graph coloring problem, and numerous combinatorial optimization tasks impacting applications at Bell Labs, AT&T, Google, and Amazon. Cryptographic systems like RSA and protocols studied by Whitfield Diffie and Martin Hellman rely on assumed hardness separating P from NP; a proof that P=NP could undermine public-key cryptography developed at institutions like University of California, Berkeley and MIT. Conversely, P≠NP would validate hardness assumptions underpinning complexity-theoretic security and guide research in approximation algorithms credited to Vijay Vazirani, David Johnson, and Umesh Vazirani.

Approaches and proof strategies

Proof attempts employ diagonalization techniques extending work of Alan Turing and Emil Post, circuit complexity lower bounds initiated by Leslie Valiant and Joan Feigenbaum-era research, algebraic methods rooted in Noga Alon’s combinatorial techniques, and Boolean Fourier analysis advanced by Ryan O'Donnell. Geometric complexity theory applies ideas from David Hilbert and representation theory influenced by Michael Atiyah and researchers like Ketan Mulmuley. Probabilistic and interactive proof frameworks leverage contributions from Shafi Goldwasser, Silvio Micali, and Oded Goldreich, while proof complexity studies use tools from Stephen Cook and János Simon. Barriers—relativization (Baker, Gill, Solovay), natural proofs (Razborov, Rudich), and algebrization (Scott Aaronson, Avi Wigderson)—guide viable strategies.

Related complexity classes and variants

Important neighboring classes include co-NP, PSPACE, EXPTIME, and BPP, with relationships explored by Lance Fortnow, Mihalis Yannakakis, and Christos Papadimitriou. Classes like #P (introduced by Leslie Valiant), RP, ZPP, and AM capture counting and randomized complexity related to NP. Descriptive complexity links P and NP to logical frameworks studied by Neil Immerman and Anuj Dawar, while parameterized complexity (e.g., FPT) developed by Rod Downey and Michael Fellows studies fine-grained variants. Hardness of approximation and inapproximability results connect to the PCP theorem contributors such as Sanjeev Arora and Luca Trevisan.

Category:Computational complexity theory