P vs NP: What Does 'NP-Complete' Actually Mean?

P is the set of problems a computer can solve in polynomial time. NP is the set of problems whose solutions can be checked in polynomial time, even if finding that solution might take far longer. Every problem in P is also in NP — if you can solve something quickly, you can certainly verify a proposed solution quickly, by just solving it yourself. The open question, and one of the most famous unsolved problems in computer science, is whether the reverse is also true: does the ability to quickly check an answer imply the ability to quickly find one?

Polynomial time, in plain terms

“Polynomial time” means the time an algorithm takes grows as a polynomial function of the input size — like n, n², or n³ — rather than exploding exponentially, like 2ⁿ. Polynomial-time algorithms are generally considered “efficient” or “tractable”: sorting a list, searching a balanced tree, or running Dijkstra’s algorithm on a graph all fall well within P. This is the same distinction that Big O notation is built to describe precisely — P is essentially “the problems with a polynomial worst-case Big O solution.”

Problems believed to sit outside P grow so fast with input size that even modest inputs become infeasible — not “slow,” but computationally out of reach on any timescale that matters.

What makes a problem “in NP”

A problem is in NP if, given a proposed solution, you can verify it’s correct in polynomial time — even if you have no efficient way to find that solution in the first place. The classic example is the subset-sum problem: given a set of numbers, does some subset add up to a target value? Finding such a subset can require checking a huge number of combinations. But if someone hands you a candidate subset, checking whether it sums to the target is trivial — just add the numbers.

That asymmetry — hard to find, easy to check — is the defining shape of an NP problem. The traveling salesman problem, in its decision form (“is there a route under length X visiting every city?”), and boolean satisfiability (“can this logical formula be made true?”) are two more of the most famous examples.

NP-hard and NP-complete

Two more terms usually show up alongside NP, and they’re often mixed up:

• NP-hard means a problem is at least as hard as every problem in NP — but it doesn’t have to be in NP itself, and it doesn’t have to be a yes/no decision problem at all.
• NP-complete means a problem is both in NP and NP-hard — it’s one of the hardest problems within NP itself. Boolean satisfiability was the first problem proven NP-complete, in a result known as the Cook–Levin theorem; thousands of other problems have since been shown NP-complete by reduction — proving they’re at least as hard as a problem already known to be NP-complete.

The practical significance of NP-completeness is enormous: if anyone finds a genuinely polynomial-time algorithm for any NP-complete problem, that algorithm can be adapted to solve every problem in NP in polynomial time — because every NP-complete problem can be reduced to every other. That single fact is why P vs NP is really one question, not thousands of separate ones.

Reductions: how one hard problem proves another is hard

Reductions are the mechanism that ties the whole theory together, and they’re worth understanding on their own. A reduction from problem A to problem B is a polynomial-time procedure that transforms any instance of A into an instance of B, such that solving the B instance also solves the original A instance. If such a reduction exists, then B is at least as hard as A — if you could solve B efficiently, you could solve A efficiently too, by reducing to B first.

This is how the list of known NP-complete problems grew from one (satisfiability, via the Cook–Levin theorem) to thousands: each new problem is shown NP-complete by exhibiting a reduction from a problem already known to be NP-complete. It also explains why NP-completeness proofs feel almost viral once the first one exists — proving a brand-new problem NP-complete no longer requires reasoning about Turing machines from scratch, just a clever transformation from an existing NP-complete problem into the new one.

Why P vs NP matters in practice

Nobody has proven whether P equals NP. Most researchers in the field believe P ≠ NP — that some problems are genuinely, fundamentally harder to solve than to check — but no proof exists either way. This isn’t just an academic curiosity: much of modern cryptography, including the schemes underlying post-quantum cryptography, implicitly relies on certain problems being hard to solve even though a candidate solution (like a private key) would be easy to verify if you had it. If P turned out to equal NP, large parts of that foundation would need to be rethought.

In everyday engineering, the practical response to “this problem is NP-hard” is rarely to keep searching for a fast exact algorithm — it’s to reach for dynamic programming or greedy heuristics that get a good-enough answer quickly, or backtracking with aggressive pruning, accepting an approximate or non-optimal solution in exchange for a solution that actually finishes running.

The takeaway

P is what a computer can solve quickly; NP is what it can check quickly, whether or not it can find the answer quickly in the first place. NP-complete problems are the hardest problems within NP, and proving even one of them solvable in polynomial time would prove all of them are. Whether P equals NP remains unproven, but the practical lesson already stands: when you’re facing a known NP-hard problem, the right move is usually an efficient approximation, not a search for an exact algorithm that almost certainly doesn’t exist.