What is the difference between NP-hard and NP-complete?

A problem is NP-hard if every NP problem reduces to it in polynomial time, but it need not itself be in NP and need not be a decision problem. A problem is NP-complete if it is both NP-hard and in NP. NP-complete problems are the hardest problems that are still in NP.

Does NP-completeness mean a problem can never be solved?

No. It means no polynomial-time algorithm is known for all inputs and likely none exists if P does not equal NP. In practice such problems are tackled with approximation algorithms, heuristics, exponential-time solvers that work on realistic instances, or by restricting to special cases.

NP-Completeness and Intractability

NP-completeness identifies the hardest problems in the class NP — those to which every NP problem reduces — and provides the standard framework for recognizing problems for which no efficient algorithm is known or likely.

Definition

A decision problem is NP-complete if it lies in NP (its yes-instances have efficiently verifiable certificates) and every problem in NP reduces to it in polynomial time; such problems are the hardest in NP, and a polynomial-time algorithm for any one would yield one for all.

Scope

This topic covers the complexity classes P and NP, polynomial-time reductions, the definitions of NP-hardness and NP-completeness, the Cook-Levin theorem establishing satisfiability as NP-complete, Karp's catalogue of NP-complete problems, and the practical consequences of intractability for algorithm design. It applies these concepts to recognizing and coping with hard problems; the broader formal theory of computational complexity classes is treated in the theory-of-computation subfield.

Core questions

What distinguishes the complexity classes P and NP?
How does a polynomial-time reduction transfer hardness from one problem to another?
What does the Cook-Levin theorem establish, and why is satisfiability central?
How is a new problem proved NP-complete by reduction from a known one?
Once a problem is shown NP-hard, what algorithmic strategies remain?

Key concepts

complexity class P
complexity class NP
polynomial-time reduction
NP-hardness
NP-completeness
Cook-Levin theorem
Boolean satisfiability (SAT)
P versus NP question

Key theories

Cook-Levin theorem: The Cook-Levin theorem proves that Boolean satisfiability (SAT) is NP-complete: every problem in NP reduces to it in polynomial time, providing the first NP-complete problem and the anchor for proving others hard.
Reducibility among combinatorial problems: Karp showed that polynomial-time reductions link many natural problems — clique, vertex cover, Hamiltonian cycle, partition and others — into a web of NP-complete problems, so each can be proved hard by reduction from another.

Clinical relevance

Recognizing that a problem is NP-complete is one of the most practically useful results in computing: it tells engineers not to expect a fast exact algorithm and to instead deploy approximation algorithms, heuristics, exact solvers tuned for typical instances, or restrictions to tractable special cases. Many scheduling, routing, packing and design problems are NP-complete.

History

Stephen Cook introduced NP-completeness in 1971, proving SAT NP-complete; Leonid Levin reached similar results independently. Richard Karp's 1972 paper showed 21 natural problems NP-complete, establishing the framework's reach. Garey and Johnson's 1979 book catalogued hundreds of NP-complete problems and became the standard reference.

Debates

P versus NP: Whether P equals NP — whether every efficiently verifiable problem is also efficiently solvable — is the foremost open problem in the field; almost all researchers conjecture P does not equal NP, but the question is unresolved and a Millennium Prize problem.

Key figures

Stephen Cook
Richard Karp
Leonid Levin
Michael Garey
David Johnson

Seminal works

cook1971
karp1972
cormen2009

Frequently asked questions

What is the difference between NP-hard and NP-complete?: A problem is NP-hard if every NP problem reduces to it in polynomial time, but it need not itself be in NP and need not be a decision problem. A problem is NP-complete if it is both NP-hard and in NP. NP-complete problems are the hardest problems that are still in NP.
Does NP-completeness mean a problem can never be solved?: No. It means no polynomial-time algorithm is known for all inputs and likely none exists if P does not equal NP. In practice such problems are tackled with approximation algorithms, heuristics, exponential-time solvers that work on realistic instances, or by restricting to special cases.