The P versus NP problem is a central open question in computer science and mathematics: can every decision problem whose “yes” answers have efficiently checkable certificates also be solved efficiently? Here, efficiency has a precise asymptotic meaning—running time bounded by a polynomial in the length of the input. The class P consists of decision problems solvable within that bound by a deterministic algorithm; NP consists of those for which a proposed certificate of a “yes” answer can be verified within that bound. Every problem in P belongs to NP, but whether the two classes are equal remains unknown.
The question concerns the relationship between finding a solution and recognizing one. A completed arrangement satisfying a large collection of constraints may be easy to check even when discovering such an arrangement appears difficult. This distinction underlies problems in scheduling, circuit design, mathematical proof, and cryptography. A proof that P equals NP would establish polynomial-time algorithms for a vast family of search and optimization tasks, though not necessarily practically useful ones. A proof that P differs from NP would establish an intrinsic limit on efficient computation, without by itself identifying the difficulty of typical real-world instances.
Formal definitions and the meaning of efficiency
The standard setting is computational complexity theory, which studies how computational resources grow with input size. A decision problem is represented as a language : a set of finite binary strings whose members are the “yes” instances. An algorithm decides if it halts on every input and correctly determines membership. The input length is the number of symbols in the encoding, not necessarily the numerical magnitude of a quantity represented by that encoding.
P is the class of languages decidable by a deterministic Turing machine in polynomial time:
Polynomial time includes bounds such as , , and , but excludes bounds such as . The definition is robust across standard models of computation: a polynomial-time computation on one conventional machine model can be simulated with polynomial overhead on another. This robustness is a major reason polynomial time became the standard theoretical criterion of tractability. It does not mean that every polynomial-time algorithm is usable in practice, or that every exponential-time algorithm is unusable on small inputs.
NP can be defined through verification. A language belongs to NP if there are a deterministic polynomial-time verifier and a polynomial such that
The string is a certificate, also called a witness. Both its length and the time needed to check it must be polynomially bounded. For a graph-coloring instance, for example, a certificate can specify a color for every vertex; the verifier checks the allowed colors and confirms that adjacent vertices have different colors. For a “no” instance, no permitted certificate makes the verifier accept.
Equivalently, NP is the class decidable by a nondeterministic Turing machine in polynomial time. Such a machine has branching computational paths and accepts if at least one path accepts. This is a mathematical model, not a claim that ordinary computers can physically explore exponentially many possibilities at once. The abbreviation NP means nondeterministic polynomial time, not “non-polynomial.”
The inclusion is immediate: a verifier can ignore its certificate and run the polynomial-time decision algorithm. The unresolved question is the reverse inclusion. Since polynomially long certificates can always be enumerated, NP problems are decidable by deterministic exponential-time search. The issue is whether that potentially enormous search can always be replaced by a polynomial-time procedure.
Historical development
The intellectual background of P versus NP combines the formalization of computation with efforts to distinguish feasible calculations from merely possible ones. In the 1930s, Alan Turing and other logicians established mathematical models of computation and demonstrated undecidable problems. Those results concern whether an algorithm exists at all. P versus NP instead concerns problems for which algorithms do exist, but for which the fastest possible algorithms may require excessive resources.
A striking precursor appears in a 1956 letter from Kurt Gödel to John von Neumann. Gödel asked about the number of computational steps needed to determine whether a formula has a proof of a specified length, and considered the implications of an unexpectedly small bound. The letter anticipated the distinction between finding a bounded proof and checking one. It did not present the modern classes P and NP, but it identified a closely related issue: whether systematic proof search could be dramatically accelerated.
During the 1960s, polynomial time emerged as a criterion for efficient computation. Alan Cobham and Jack Edmonds independently helped articulate its significance in work published in 1965. Edmonds’s polynomial-time algorithm for maximum matching supplied an important example of a combinatorial problem that could be solved efficiently despite an apparently enormous collection of candidate solutions. Juris Hartmanis and Richard Stearns’s 1965 work on the computational complexity of algorithms helped establish the broader framework of resource-bounded complexity classes.
The decisive development came in 1971, when Stephen Cook showed that propositional satisfiability could represent every problem in NP through a polynomial-time transformation. Leonid Levin independently developed a closely related theory of universal search problems in work published in 1973. Their results are now associated with the Cook–Levin theorem. The theorem transformed the general P versus NP question into the question of whether one particular logical problem has a polynomial-time algorithm.
Richard Karp’s 1972 paper “Reducibility Among Combinatorial Problems” demonstrated the breadth of the resulting theory by establishing the completeness of 21 combinatorial problems. Problems arising in graphs, scheduling, covering, and numerical selection could be connected through efficient transformations. This made complexity theory a practical language for classifying algorithmic difficulty, rather than only a study of machine models. In 2000, the Clay Mathematics Institute designated P versus NP as one of its seven Millennium Prize Problems, attaching a US$1 million prize to a qualifying solution.
Reductions and NP-completeness
The central organizing tool is the polynomial-time reduction. For decision problems and , a polynomial-time many-one reduction from to is a function , computable in polynomial time, such that
The notation expresses that an instance of can be translated into an equivalent instance of efficiently. A polynomial-time algorithm for , combined with the translation, therefore yields a polynomial-time algorithm for . The direction matters: reducing a difficult problem to a new problem provides evidence of the new problem’s difficulty, not of its ease.
A problem is NP-hard if every problem in NP reduces to it. It is NP-complete if it is both NP-hard and a member of NP. NP-complete problems are therefore universal representatives of NP under these reductions. They are not necessarily the hardest problems in all of computation: many problems outside NP require greater resources, and some are undecidable. Moreover, an NP-hard problem need not belong to NP; the term also applies to optimization tasks and to problems whose solutions do not have polynomially checkable certificates.
The Boolean satisfiability problem, or SAT, asks whether a Boolean formula has an assignment of truth values making it true. The Cook–Levin theorem establishes that SAT is NP-complete. Its underlying construction encodes a polynomial-time nondeterministic computation as a polynomial-size Boolean formula. Variables describe such features as tape contents, machine states, and head positions at successive times. Constraints enforce a valid initial configuration, legal transitions, and an accepting outcome. A satisfying assignment exists exactly when an accepting computation exists.
The theorem yields the fundamental equivalence
Once SAT is known to be NP-complete, another problem can be proved NP-complete by showing that it belongs to NP and giving a polynomial-time reduction from SAT, or from another established NP-complete problem. There is no need to encode every NP computation afresh. This chaining of reductions explains how the classification spread across many fields.
A completeness proof is not an unconditional proof of intractability. It establishes that a polynomial-time algorithm for the target problem would solve every problem in NP efficiently. Since P versus NP is unresolved, NP-completeness alone does not prove that such an algorithm is impossible. Nor does it show that every instance is difficult. Reductions preserve the existence of solutions across instances and establish worst-case relationships between entire problem families.
Representative problems and the importance of encoding
Examples from graph theory make the distinction between solving and checking concrete. The clique problem asks whether a graph contains vertices that are all pairwise adjacent. A certificate lists the vertices, and verification checks at most pairs. The Hamiltonian cycle problem asks whether a graph has a cycle visiting every vertex exactly once; a proposed ordering can likewise be checked efficiently. Both decision problems are NP-complete, although their certificates are straightforward.
The decision version of the traveling salesperson problem asks whether a tour through all specified locations has total cost at most a given threshold. For explicitly encoded integer edge costs, a verifier checks that the tour visits each location once and adds its costs. The optimization version asks for a minimum-cost tour. These are different computational tasks, but closely connected: an efficient exact optimizer answers the decision question, while repeated decision queries can locate the optimum when the costs have suitable finite encodings.
Numerical encodings can change the complexity analysis substantially. In the subset sum problem, the input consists of integers and a target ; the question is whether some subset sums to . For nonnegative integers, a dynamic programming algorithm can maintain which sums up to are reachable, using time on the order of . This is not polynomial in the length of a binary-encoded input, because writing requires only about bits. A running time polynomial in the numerical values rather than their encoding lengths is called pseudopolynomial.
Small changes in restrictions can also separate tractable and NP-complete problems. Satisfiability for formulas in conjunctive normal form with at most two literals per clause, called 2-SAT, is solvable in polynomial time through an implication graph. Allowing at most three literals per clause gives 3-SAT, which is NP-complete. Graph 2-colorability can be tested by checking whether the graph is bipartite, whereas graph 3-colorability is NP-complete. These boundaries show why complexity classifications must specify the precise problem rather than a broad application area.
Other apparently similar problems require entirely different methods. The shortest path problem has polynomial-time algorithms under standard formulations, even though the number of possible paths can be enormous. Maximum matching is also polynomial-time solvable. The number of conceivable candidates therefore does not establish computational hardness: structural properties may permit an algorithm to avoid enumerating them. NP-completeness proofs capture a stronger obstacle than the observation that brute-force search is expensive.
Decision, search, optimization, and proof
P and NP are formally classes of decision problems, but their significance extends to finding objects. For many NP-complete problems, decision and search are connected by self-reducibility. Suppose a polynomial-time SAT algorithm is available. To construct a satisfying assignment, first test whether the formula is satisfiable. Then fix one variable to false and test the restricted formula. If satisfiability remains possible, retain that value; otherwise set the variable to true. Repeating this procedure produces a satisfying assignment with only a linear number of decision queries.
The same principle extends to arbitrary polynomially checkable witnesses if P equals NP. Given an input and a proposed prefix of a certificate, ask whether that prefix can be extended to an accepting certificate. This extension question belongs to NP, because the missing suffix can be supplied and checked. Under P equals NP, it can therefore be answered deterministically in polynomial time. Successively extending the prefix finds a certificate whenever one exists. In standard function-class terminology, the corresponding equality is often expressed as .
Exact mathematical optimization can often be handled by combining decision queries with witness recovery. If feasible solutions have polynomial-length descriptions and integer-valued objectives of polynomial bit length, threshold questions can identify the optimum through binary search over the possible objective values. The resulting number of queries is polynomial in the input length, even when the numerical range is exponentially large. Additional queries can then reconstruct a solution attaining that value. Optimization over arbitrary real numbers requires more care, because representation and requested precision affect what counts as an input or output.
Mathematical proof provides another important example. In a fixed formal proof system whose proofs can be checked in polynomial time, the question “Does this statement have a proof of at most symbols?” belongs to NP when is encoded in unary, or is otherwise bounded polynomially in the total input length. A certificate is the proof itself. If P equals NP, such bounded proofs could be found in polynomial time in the statement length and the permitted proof length.
This conclusion does not imply an efficient procedure for all mathematical truth. Proofs may be extraordinarily long, some statements may be unprovable in a chosen formal system, and unrestricted theoremhood can be undecidable. The halting problem remains undecidable regardless of the answer to P versus NP. Similarly, a proof assistant or a system for formal verification may encounter problems beyond NP, depending on its logic and specification language. The reach of P equals NP is determined by the availability of polynomially bounded certificates, not by the informal description “reasoning problem.”
Consequences for cryptography and information processing
A major consequence of P equals NP would be the failure of standard computational one-way functions. Informally, these are functions that can be computed efficiently but are difficult to invert on inputs drawn from a specified distribution. Given an output and a suitable polynomial bound on the preimage length, checking a candidate preimage is efficient. The question of whether a preimage with a specified prefix exists is therefore in NP. If P equals NP, prefix-by-prefix search can find a preimage in polynomial time.
This would undermine the usual asymptotic security foundations of public-key encryption, digital signatures, and many other cryptographic constructions. In the RSA cryptosystem, for example, factoring the public modulus enables recovery of information needed for the private operation. Integer factorization has efficiently checkable outputs, and P equals NP would yield a polynomial-time factoring algorithm. More generally, the consequences would not be limited to one named number-theoretic problem: efficient witness search would defeat the inversion hardness required by conventional one-way functions.
The reverse implication does not hold as an established theorem. P differing from NP would show that some problems in NP lack polynomial-time algorithms in the worst case, but cryptography requires appropriately distributed instances to remain difficult for adversaries. A problem might have rare hard instances and be easy almost everywhere else. The study of average-case complexity distinguishes this distributional difficulty from worst-case difficulty. The existence of one-way functions implies P differs from NP; whether P differing from NP is sufficient for one-way functions is unknown.
Not all forms of security rest on computational hardness. A correctly used one-time pad provides information-theoretic secrecy when its key is uniformly random, secret, as long as the message, and never reused. That guarantee would not be invalidated by P equals NP. Conversely, even under P differing from NP, practical systems may fail through implementation errors, key disclosure, or protocol weaknesses. Complexity-theoretic assumptions address particular computational attacks, not every aspect of cybersecurity.
Polynomial-time solvability would also have implications for scheduling, automated planning, circuit design, and some tasks in machine learning. The scope requires care. P equals NP would not eliminate unavailable data, statistical uncertainty, model misspecification, or physical limits on measurement. Nor would it guarantee useful running times: an algorithm requiring operations is polynomial but impractical for ordinary inputs. The distinction between an asymptotic breakthrough and an immediately deployable technology is essential when interpreting the problem’s consequences.
Relationships with other complexity classes
NP is one part of a larger landscape of computational resources. The class coNP consists of complements of NP languages. For example, a Boolean formula is in the language UNSAT exactly when it has no satisfying assignment. SAT has short certificates of satisfiability; whether every unsatisfiable formula has a polynomial-size certificate checkable by a fixed polynomial-time verifier is equivalent to asking whether NP equals coNP. P is closed under complementation, so P equals NP would imply .
The converse is not known: NP could equal coNP without equaling P. This distinction matters when interpreting certificates of nonexistence. A method that efficiently verifies “no” answers for all NP problems would establish NP equals coNP, but it would not automatically supply a deterministic polynomial-time method for finding those certificates. Integer factorization illustrates another subtlety. Suitable decision formulations belong to both NP and coNP, yet no classical polynomial-time factoring algorithm is known, and factoring is not known to be NP-complete.
The polynomial hierarchy extends NP by allowing a fixed number of alternating existential and universal quantifier blocks over polynomial-length strings. NP corresponds to an existential block; coNP corresponds to a universal block. Higher levels describe statements such as “there exists a choice such that, for every response, a polynomial-time condition holds.” If P equals NP, the entire polynomial hierarchy collapses to P. A collapse at some higher level, however, need not establish P equals NP.
Other familiar inclusions are
where PSPACE allows polynomially bounded memory and EXPTIME allows deterministic time . The deterministic time hierarchy theorem proves . It does not identify which intermediate inclusion is strict. Thus, rigorous separations between some resource bounds are known even though the specific comparison between P and NP remains unresolved.
Randomness and quantum mechanics raise separate questions. BPP captures bounded-error randomized polynomial-time computation; whether BPP equals P is unknown. BQP captures bounded-error polynomial-time quantum computation. A quantum computer can factor integers in polynomial time using Shor’s algorithm, but no polynomial-time quantum algorithm is known for NP-complete problems. Grover’s algorithm provides a quadratic improvement for unstructured search, not a general conversion from exponential to polynomial time. Since P and NP are defined through classical deterministic and nondeterministic computation, a quantum speedup would not by itself settle their relationship.
Practical algorithms, approximation, and restricted instances
NP-completeness does not prevent useful computation. Modern SAT solvers routinely handle many large instances arising from hardware verification, software analysis, and planning. They combine techniques such as unit propagation, clause learning, branching heuristics, and restarts. Their success reflects exploitable structure in particular instance families. It does not establish a polynomial worst-case bound, and no solver is known to avoid difficult instances throughout the full NP-complete problem class.
An approximation algorithm relaxes the demand for an exact optimum while providing a guarantee on solution quality. For a minimization problem, an approximation ratio typically means that the returned value is at most times the optimum. The metric traveling salesperson problem, where distances satisfy the triangle inequality, admits Christofides’s polynomial-time -approximation algorithm from 1976. Such a guarantee does not solve the exact optimization problem and does not contradict its NP-hardness.
Approximation itself can be computationally difficult. The PCP theorem, established through work in the early 1990s, characterizes NP using probabilistically checkable proofs: a verifier uses logarithmically many random bits and inspects only a constant number of proof positions. Through gap-producing reductions, it yields results showing that certain approximation guarantees would imply P equals NP. For example, sufficiently accurate approximation of some constraint-satisfaction objectives is NP-hard. Exact solvability and approximability are therefore separate dimensions of complexity.
Parameterized complexity studies running times in terms of both overall input length and a structural parameter . A problem is fixed-parameter tractable if it has an algorithm running in time, with independent of . Vertex cover, which asks whether at most vertices can touch every edge, is NP-complete when is unrestricted but fixed-parameter tractable with respect to . This can be useful when the relevant parameter is small, without making the general problem polynomial-time solvable.
Restrictions on graph structure, clause form, numerical size, or other properties can likewise create tractable subclasses. Tree-like graphs support efficient dynamic programming for many otherwise difficult tasks. A heuristic may also produce excellent solutions quickly without a universal quality guarantee. These approaches answer practical questions that P versus NP deliberately abstracts away from: which instances occur, what structure they contain, whether near-optimal answers suffice, and how much time is available. Experimental success on benchmarks is consequently neither a proof of P equals NP nor evidence establishing a universal lower bound.
Lower bounds and barriers to existing proof methods
To prove P differs from NP, it would suffice to show that one NP problem—such as SAT—cannot be decided by any deterministic polynomial-time algorithm. This is a universal claim over all such algorithms, including ones not yet conceived. Showing that brute force is exponential, or that a particular family of methods fails, is therefore insufficient. The central difficulty is obtaining lower bounds that apply to unrestricted computation rather than to a limited algorithmic technique.
One important approach studies circuit complexity. A Boolean circuit computes a function using interconnected logic gates, and its size measures the number of gates. Every polynomial-time algorithm gives rise to polynomial-size circuits, one for each input length. Consequently, a superpolynomial lower bound on general Boolean circuit size for a language in NP would imply P differs from NP. This target is stronger than necessary, because polynomial-size circuit families need not have an efficient uniform procedure for constructing them. Strong lower bounds are known for restricted circuits, including bounded-depth circuits with specified gate types, but not for unrestricted circuits computing an NP-complete language.
A major obstacle is relativization. In 1975, Theodore Baker, John Gill, and Robert Solovay constructed oracles and such that
An oracle supplies instantaneous answers to membership queries for a designated language. A proof method that remains valid when both machine classes receive the same arbitrary oracle cannot settle P versus NP, because oracle worlds exhibit both outcomes. This explains the limitations of many straightforward diagonalization arguments, though it does not make diagonalization irrelevant to all possible approaches.
Alexander Razborov and Steven Rudich identified another barrier in their 1997 work on natural proofs. Roughly, many known circuit lower-bound arguments identify properties of Boolean functions that are efficiently recognizable from truth tables, hold for a sufficiently large fraction of functions, and exclude functions computable by small circuits. Under strong pseudorandomness assumptions, properties with all these features cannot prove the desired general circuit lower bounds. This is a conditional limitation on a broad family of proof strategies, not a theorem that circuit lower bounds are impossible.
Scott Aaronson and Avi Wigderson introduced algebrization in 2008. Their framework captures techniques that combine oracle access with certain algebraic extensions, including methods that go beyond ordinary relativization. They showed that even this broader collection of techniques faces limitations for major complexity questions. Relativization, natural proofs, and algebrization are distinct barriers with different hypotheses. None establishes that P versus NP is independent of standard mathematical axioms, and none rules out a proof that uses sufficiently different ideas.
Conditional hypotheses and current lines of investigation
The assumption P differs from NP states only that some NP problem has no polynomial-time algorithm. It does not specify a quantitative lower bound such as , nor does it exclude subexponential algorithms. Finer-grained research therefore uses stronger hypotheses. The Exponential Time Hypothesis, associated with work by Russell Impagliazzo and Ramamohan Paturi, asserts a positive exponential-time lower-bound rate for 3-SAT measured by the number of variables. It implies P differs from NP, while supporting more specific conditional running-time lower bounds.
The Strong Exponential Time Hypothesis makes a sharper claim about -SAT as clause width grows. Informally, for every , there is some for which -SAT cannot be solved in time , apart from polynomial factors in input size. Such hypotheses allow researchers to investigate whether known exponential algorithms can be substantially improved and to transfer conditional limitations to other tasks. They remain assumptions, not established lower bounds, and their precise formulations must specify the permitted computational model.
Another direction studies connections between algorithm design and lower bounds. An algorithm can sometimes reveal enough structure to prove that a class of circuits is limited. Ryan Williams’s work, announced in 2010 and subsequently published, used faster-than-exhaustive satisfiability algorithms for certain circuits to establish that NEXP is not contained in nonuniform ACC. ACC consists of constant-depth, polynomial-size circuits with AND, OR, NOT, and modular counting gates. This does not settle P versus NP, but it demonstrates a rigorous route from improved algorithms to significant circuit lower bounds.
Proof complexity investigates the size of formal proofs of unsatisfiability. For a fixed proof system, lower bounds can explain why some automated reasoning procedures require long proofs. More broadly, a polynomially bounded Cook–Reckhow propositional proof system exists if and only if NP equals coNP. Accordingly, proving that no such system exists would imply NP differs from coNP and hence P differs from NP. Lower bounds for particular systems, such as resolution, are important but do not establish this universal conclusion, because stronger systems may have shorter proofs.
A proposed resolution must ultimately address the full definitions. A proof of equality must establish a correct deterministic polynomial-time algorithm for an NP-complete problem, with running time measured against the actual input encoding. A proof of inequality must rule out every deterministic polynomial-time algorithm for at least one NP language. Claims based only on benchmark performance, exhaustive-search analysis, special instance restrictions, or an informal appeal to an enormous search space do not meet those requirements. The unresolved core is whether all efficiently verifiable existence questions admit efficient deterministic decisions.