AlegsaOnline.com

P versus NP: the central question in computational complexity

An overview of the P versus NP problem: definitions, intuitive examples, historical milestones, consequences of either outcome, and current research directions in complexity theory.

Author: Leandro Alegsa Creation date: September 6, 2021 Last updated: June 3, 2026

en.wikipedia.org · Public domain

Overview

The P versus NP question asks whether every problem whose solutions can be checked quickly can also be solved quickly. In formal terms, it asks whether the complexity classes P and NP are equal. P (polynomial time) contains decision problems that a deterministic algorithm can solve in time bounded by a polynomial function of the input size. NP (nondeterministic polynomial time) contains decision problems for which a purported solution (a certificate) can be verified in polynomial time. It is straightforward that P is a subset of NP, because any problem that can be solved quickly yields a certificate (the computed solution) that can also be verified quickly. The open question is whether NP contains problems that are inherently harder to solve than to verify, i.e., whether P < NP.

Formal meaning and intuition

A decision problem is in P if there exists a deterministic algorithm whose running time is O(n^k) for some fixed k, where n measures the input size. A problem is in NP if, for every input for which the correct answer is "yes," there exists a short witness that a deterministic verifier can check in polynomial time. Equivalently, NP is the class of problems solvable in polynomial time by a nondeterministic machine. Intuitively, NP contains tasks like "Does there exist a route visiting each city once with total distance ≤ B?" (the decision form of the traveling salesman problem), where a proposed route is easy to verify but finding such a route may be hard.

Important subclasses and examples

Within NP, certain problems are singled out as NP-complete: they are in NP and as hard as any other problem in NP under polynomial-time reductions. If any NP-complete problem is in P, then P = NP. The Boolean satisfiability problem (SAT) was the first problem proved NP-complete (the Cook–Levin theorem). Other canonical NP-complete problems include:

3-SAT (a restricted form of SAT)
Graph Hamiltonian cycle and Hamiltonian path
Subset sum and integer partition variants
Graph coloring and clique decision problems
Decision versions of many combinatorial optimization problems (e.g., traveling salesman)

Historical context and significance

The distinction between easy-to-solve and easy-to-verify problems emerged in mid-20th-century theoretical computer science as researchers formalized algorithms and computation. The classification of NP-complete problems showed that many seemingly unrelated practical problems share the same theoretical difficulty. The question whether P equals NP became one of the most important unresolved problems in mathematics and computer science, with deep implications for algorithm design, cryptography, and our understanding of computation.

Consequences of either outcome

P=NP The resolution of P versus NP would have far-reaching consequences. If P = NP, many tasks that now require clever heuristics or exponential-time search—such as certain optimization problems, automated theorem proving, and some scheduling tasks—would admit polynomial-time algorithms in principle. This could revolutionize fields that depend on solving hard computational problems, but the practical impact would depend on the degree of the polynomial and constant factors. Conversely, if P ≠ NP, it would provide a firm theoretical foundation for why a wide class of problems resists efficient algorithms, supporting the security assumptions behind many cryptographic systems and justifying the focus on approximation and heuristics for hard problems.

Progress, barriers, and modern research directions

Despite decades of effort, no proof has settled the question. Researchers have achieved many partial results: separations in restricted computational models, completeness results, and conditional implications. Work on circuit complexity seeks lower bounds that might imply P ≠ NP, while proof complexity examines the difficulty of formal proofs. Several meta-level barriers have been identified that explain why standard techniques fail to resolve the problem in full generality—examples include relativization, natural proofs, and algebrization barriers. Other active areas include the study of probabilistically checkable proofs (PCPs), interactive proofs, and fine-grained complexity, which refines the understanding of hardness within polynomial time.

Why the problem matters today

$P\neq NP$ Beyond theoretical interest, the P versus NP question guides practical choices in computer science: whether to seek exact polynomial-time algorithms, design approximation algorithms, or rely on randomized heuristics. It influences cryptography, optimization, artificial intelligence, and many applied domains. The problem remains open and is a focal point of research in computational complexity, reflecting fundamental limits on what can be computed efficiently.

History

The problem was recognized in the early 1970s due to independent work by Stephen Cook and Leonid Levin.

The P-NP problem is considered one of the most important unsolved problems in computer science and was included in the list of Millennium Problems by the Clay Mathematics Institute.

As became known later, a formulation of the problem can already be found in a letter by Kurt Gödel, which he sent to John von Neumann shortly before his death (on March 20, 1956). Another early formulation is found in a letter from John Forbes Nash to the National Security Agency in 1955, concerning cryptography.

P and NP

Complexity theory classifies problems that can be computed by computers according to the amount of time or memory required to solve them, or more precisely, according to how fast the effort grows with the size of the problem. For example, one problem is sorting index cards. It is now possible to examine how the time required changes when a stack twice as large is sorted.

The measure of computational effort used here is the number of computational steps required by the algorithm to solve a problem (time complexity). In order to specify the computational effort unambiguously, formal machine models are also required to represent the solution algorithms. A frequently used model is the deterministic Turing machine, which can be regarded as the abstraction of a real computer.

P

→ Main article: P (complexity class)

One of the problem categories is the complexity class . It contains the problems for which there exists a deterministic Turing machine that solves the problem in polynomial time. That is, there exists a polynomial $f(n)=n^{k}+c$ with $c,k\in \mathbb {N}$ , so that for no problem instance (with length of the input) does the Turing machine need more f(n) computational steps than Problems from are thus deterministically solvable in polynomial time.

The above sorting problem is in P because there are algorithms that sorted a number of records (index cards) in a time bounded by a quadratic function in Another example of a problem in is the circuit evaluation problem.

The difference between a Turing machine and real computers does not matter here, because any algorithm that solves a problem in polynomial time on a real computer can also be implemented in polynomial time with a Turing machine (though the degree of the polynomial limiting the running time will usually be higher).

NP

→ Main article: NP (complexity class)

Another machine model is the non-deterministic Turing machine (NTM), it is a generalization of the deterministic variant. An NTM can have several possibilities to continue its computation in a situation, so the computational path is not always uniquely determined. It is a theoretical model, there are no real-world computers that can branch their computational path in such a way. Its utility in this context is that it can be used to define another complexity class , which contains many problems of practical interest that are not yet known to lie in

is defined as the set of problems solvable by an NTM in polynomial time. The deterministic Turing machine is a special case of the NTM, it does not branch the computational path. Therefore, is a subset of .

One can define equivalently as the set of problems of which it is possible to decide in polynomial time using a deterministic Turing machine whether a proposed solution holds. For example, no deterministic algorithm is currently known to factorize a given number in polynomial time. However, it is very easy to test whether a proposed factor divides the number without a remainder and is therefore a factor of the number.

Is P=NP?

It is unknown whether the two classes and are identical, i.e., whether the hardest problems in the class are also efficiently solvable by deterministic machines. To formally capture the notion of "hardest problem in ", the notions of NP-completeness and NP-hardness were introduced. A problem X is NP-hard if one can reduce every problem in to X by polynomial-time reduction. Should one find an NP-hard problem X that can be solved deterministically in polynomial time, one could also solve any problem in deterministically polynomially by reducing it back to X, and it would be $P=NP$ shown A problem that lies in and is NP-hard is called NP-complete.

An illustrative NP-complete problem is the knapsack problem: a container of a certain size is to be filled with a selection of given items in such a way that the contents are as valuable as possible without exceeding the capacity of the container. Another important example is the satisfiability problem in propositional logic.

It was also shown that if $P\neq NP$ and thus the NP-complete problems are not in , then in there are also problems that are neither NP-complete nor in , that is, intermediate in difficulty. A candidate for such a problem is the graph isomorphism problem, which so far is not known to be in , nor to be NP-complete.

The complexity class NP, under the assumption P≠NP. In this case, NP also contains problems above P that are not NP-complete.

Relationship of problems in P and NP and of NP-severe and NP-complete

Questions and Answers

Q: What is the Millennium Problem?

A: The Millennium Problem is one of the most important and challenging mathematical problems of this century that address the issue of whether every problem that is easy for computers to verify is also easy to solve.

Q: How can we classify math problems?

A: Math problems can be classified as P or NP problems based on whether they are solvable in finite polynomial time.

Q: What is the difference between P and NP problems?

A: P problems are relatively fast and "easy" for computers to solve, while NP problems are fast and "easy" for computers to check, but not necessarily easy to solve.

Q: Who introduced the P versus NP problem?

A: Stephen Cook introduced the P versus NP problem in 1971 in his article "The complexity of theorem proving procedures."

Q: Why is the P versus NP problem important?

A: The P versus NP problem is considered the most important open problem in computer science and is one of the seven Millennium Prize Problems, with a $1,000,000 prize for a solution that invites a published recognition by the Clay Institute and presumably one(s) that changes the whole of mathematics.

Q: Is it possible to solve an NP-complete problem in quadratic or linear time?

A: In 1956, Kurt Gödel wrote a letter to John von Neumann asking whether a certain NP-complete problem could be solved in quadratic or linear time.

Q: Why do many mathematicians hope the Millennium Problems are interconnected?

A: Many of the Millennium Problems touch upon related issues, and it is the dream of many mathematicians to invent unifying theories.