iTechGuides is reader-supported. When you buy through links on our site, we may earn an affiliate commission. As an Amazon Associate I earn from qualifying purchases. Learn more
P vs NP asks whether every problem whose proposed answer can be checked in polynomial time can also be solved in polynomial time. We know that P is contained in NP, but whether P equals NP remains open: the Clay Mathematics Institute currently lists it as unsolved.
What do P and NP mean?
In computer science, P and NP are classes of decision problems: questions whose answers are yes or no. “Polynomial time” describes how an algorithm’s running time grows with the length of its input. It is a formal measure of efficiency, not a promise that an algorithm will be fast for every practical input.
P: problems that can be solved in polynomial time
P contains decision problems that a deterministic algorithm can decide in polynomial time. Informally, the algorithm can determine the yes-or-no answer within a number of steps bounded by a polynomial in the input length.
NP: problems with efficiently checkable certificates
NP contains problems decidable by a nondeterministic polynomial-time algorithm. Equivalently, for a yes instance, there is a certificate—a proposed solution of polynomial length—that a deterministic verifier can check in polynomial time. NP does not mean “not polynomial,” and membership in NP does not mean a problem is known to be difficult. Some NP problems are already in P.
#1 Best Overall
This certificate view captures the familiar intuition: finding a solution may seem harder than checking a proposed one. The formal definition is about polynomial time and a specified computational model, not an absolute judgment about what feels hard.
Why is checking different from finding?
Example: a Hamiltonian path
A Hamiltonian path is a route through a graph that visits every vertex exactly once. If someone proposes a route, checking that it starts and ends at vertices in the graph, follows valid edges, and visits each vertex once is straightforward. Finding such a route may appear more challenging. The Clay Mathematics Institute uses this as an illustration of the P vs NP question; it is not a proof that finding a Hamiltonian path lies outside P.
The question is whether there is always a polynomial-time method for finding an answer whenever a proposed answer can be verified in polynomial time. An example can make the distinction intuitive, but it cannot establish a general lower bound—that is, prove that no polynomial-time algorithm exists.
What is known about P vs NP?
Every problem in P is also in NP: if an algorithm can determine the answer in polynomial time, a verifier can check that result in polynomial time. So the established relationship is P ⊆ NP. The unanswered question is whether NP ⊆ P as well.
- If P = NP: every NP decision problem would have a polynomial-time algorithm.
- If P ≠ NP: at least one problem with efficiently checkable certificates would have no polynomial-time decision algorithm.
Neither possibility has been proved. The Clay Mathematics Institute currently lists P vs NP as unsolved. Stephen Cook and Leonid Levin formulated the problem independently in 1971, according to Clay’s overview.
Why does the question matter?
A proof would clarify the limits of efficient computation: whether efficient verification always comes with efficient solution methods, or whether some problems have a fundamental gap between the two. That distinction matters across theoretical computer science and mathematics, including the study of algorithms and complexity.
It would not follow that every practical optimization problem becomes easy, or that a mathematical result automatically yields useful software. Polynomial-time algorithms can still be impractical when their degree or constants are large, and the definitions concern asymptotic worst-case growth rather than performance on every real-world instance.
The Tool Desk
Outbyte PC Repair FREERepair Windows errors before they cause bigger problemsFix Now →Outbyte Driver Updater FREEScan for outdated or missing drivers - takes under a minuteDriver Scan →Cryptography is also connected to computational hardness, but a P = NP proof would not by itself establish that all encryption is instantly broken. The consequences would depend on the algorithms, problem reductions, and practical efficiency involved; asymptotic tractability alone does not guarantee a usable attack.
Best Value
How is the problem studied today?
The Clay Mathematics Institute’s 2025 workshop on P vs NP and complexity lower bounds described ongoing work in areas including circuit lower bounds, meta-complexity, algebraic and geometric complexity theory, hardness of approximation, and proof complexity. These are active research directions, not evidence that the central question has been settled.
For a formal treatment of the definitions and computational model, see the Clay Mathematics Institute’s P vs NP overview and Stephen Cook’s official problem description. Clay’s Millennium Prize Problems page identifies the problem’s unsolved status; its 2025 workshop page outlines some current research themes.
Quick Recap
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
