NP-hardness
NP-hardness is a classification of computational problems according to their relationship with the complexity class NP. Informally, a problem is NP-hard when an efficient method for solving it would yield efficient methods for every problem in NP. The classification does not require the problem itself to belong to NP, to have efficiently verifiable solutions, or even to be a decidable problem.
The meaning of NP-hardness depends on a specified form of computational reduction. In its standard usage, the relevant relation is polynomial-time many-one reducibility. A decision problem (H) is NP-hard under this relation when every language (L) in NP admits a polynomial-time computable function (f) satisfying
[ x \in L \iff f(x) \in H. ]
The function (f) transforms each instance of (L) into one instance of (H) while preserving the answer. Because the transformation has polynomial running time, it cannot perform unrestricted computation before presenting the resulting instance.
An NP-hard decision problem that also belongs to NP is NP-complete. Thus, NP-completeness is an internal completeness condition for NP, whereas NP-hardness is a lower-bound classification that can apply to problems outside that class.
Formal position in complexity theory
The class NP consists of decision problems whose affirmative instances possess certificates verifiable by a deterministic Turing machine in polynomial time. NP-hardness instead describes the relative expressive power of a target problem under an allowed reduction. These two definitions concern different properties: membership specifies an upper bound on verification, while hardness specifies that the target represents every problem in a source class.
For a decision problem (H), the standard relationship is
[
H \text{ is NP-complete}
\iff
H \in \mathrm{NP}
\ \text{and}
H \text{ is NP-hard}.
]
This distinction permits NP-hard problems to occur arbitrarily high in the hierarchy of computational difficulty. A PSPACE-complete problem is NP-hard under polynomial-time reductions because (\mathrm{NP}\subseteq\mathrm{PSPACE}). Certain undecidable languages are also NP-hard, although their undecidability is a stronger obstruction than the unproved absence of polynomial-time algorithms.
If an NP-hard decision problem belongs to P, then every language in NP also belongs to P, and consequently (P=NP). The converse does not place every NP-hard problem in P because the definition of hardness alone supplies no upper complexity bound. Even under (P=NP), an NP-hard problem outside the decidable languages would remain outside P.
Membership of an NP-hard problem in co-NP would also have a major class-theoretic consequence. Since co-NP is closed under polynomial-time preimages, such membership would imply (\mathrm{NP}\subseteq\mathrm{co\text{-}NP}), and closure under complementation would then give (\mathrm{NP}=\mathrm{co\text{-}NP}).
Historical development
The mathematical basis of NP-hardness arose from the early theory of polynomial-time reducibility. In 1971, Stephen Cook proved that the Boolean satisfiability problem captures every problem in NP through polynomial-time reductions. Leonid Levin independently obtained the corresponding result within his theory of universal search, producing what became known as the Cook–Levin theorem.
In 1972, Richard Karp demonstrated that polynomial-time reductions connect satisfiability to a broad family of combinatorial decision problems. His reductions established twenty-one NP-complete problems and showed that completeness was a structural phenomenon rather than an isolated property of propositional formulas.
The modern terminology was consolidated during a 1974 correspondence on complexity-theoretic vocabulary organized by Donald Knuth. Within that exchange, You Watanabe formulated the term “NP-hard” for problems to which every NP problem reduces, while the term “NP-complete” was restricted to NP-hard problems that are themselves members of NP. This terminological division separated relative lower bounds from class membership and became standard in subsequent complexity literature.
Later work refined the classification by varying the permitted reductions and the representation of numerical data. These refinements did not replace the original concept, but they made explicit that hardness is always relative to a computational model and a reduction relation.
Reductions and inheritance of hardness
Polynomial-time many-one reducibility is transitive. If (A\leq_{\mathrm p}B) and (B\leq_{\mathrm p}C), then the composition of the two reduction functions is computable in polynomial time, giving (A\leq_{\mathrm p}C). Consequently, hardness propagates forward through reduction chains.
Most NP-hardness theorems rely on this inheritance property. A previously established NP-hard problem is reduced to a target problem, and the resulting composition transfers reductions from all of NP to that target. The reverse direction has no such implication: a reduction from the target to an NP-hard problem establishes an upper comparison rather than NP-hardness of the target.
The particular reduction type affects the resulting classification. A polynomial-time Turing reduction may query an oracle repeatedly and may choose later queries according to earlier answers. A many-one reduction instead produces a single target instance whose answer determines the original answer. Hardness under Turing reductions is therefore generally a weaker claim than hardness under many-one reductions, since the former permits a more powerful reduction mechanism.
Other notions preserve additional structure. Parsimonious reductions preserve the number of solutions and are relevant to counting complexity. Approximation-preserving reductions transfer quantitative approximation guarantees between optimization problems. Logarithmic-space reductions restrict the memory used by the transformation and support completeness results within classes below P.
Decision and optimization formulations
NP was defined as a class of decision problems, but the expression “NP-hard” is also applied to optimization problems through explicitly chosen reductions or through their associated decision versions. For example, the decision version of the travelling salesperson problem asks whether a tour exists whose total length does not exceed a specified threshold. This problem is NP-complete under standard encodings.
The optimization version asks for a minimum-length tour rather than a yes-or-no answer. An exact polynomial-time optimization algorithm would solve the decision version by computing the optimum and comparing it with the threshold, so the optimization problem is NP-hard. It is not formally NP-complete because NP, as conventionally defined, contains languages rather than function or optimization problems.
The converse relationship often uses polynomially many threshold queries. When objective values have polynomially bounded binary descriptions, a decision oracle can determine an optimum by searching over possible values. Recovering an actual optimal object may require additional queries that progressively constrain its components. These equivalences depend on the encoding and cannot be inferred solely from the informal similarity between two formulations.
Strong and weak NP-hardness
Numerical problems can receive their apparent difficulty partly from binary encoding. An integer of value (N) occupies only (O(\log N)) input symbols in binary, so an algorithm polynomial in (N) may still be exponential in the encoded input length. Such an algorithm is called pseudo-polynomial.
A problem is weakly NP-hard when its hardness proof depends on numerical magnitudes that may grow exponentially relative to their binary representations. The subset sum problem provides the standard example because it has a dynamic-programming algorithm whose running time is polynomial in the target value but not necessarily in the target’s bit length.
Strong NP-hardness persists when the numerical quantities are bounded by a polynomial in the size of the remaining input. This stronger condition rules out pseudo-polynomial algorithms unless (P=NP). The distinction concerns encoded magnitude rather than a separate reduction direction, and it is principally relevant to problems whose inputs contain integers.
Interpretive limits
NP-hardness is a worst-case asymptotic classification. It states that every NP problem can be represented within the target problem by reductions whose running times and output lengths are polynomially bounded. It does not state that every instance is difficult, nor does it determine the behavior of a particular implementation on a particular input distribution.
The classification also provides no unconditional exponential lower bound. Under the current state of complexity theory, NP-hardness excludes polynomial-time solvability only under the assumption that (P\ne NP). A superpolynomial lower bound for an unrestricted NP-hard problem in a standard general-purpose model would resolve central open questions concerning computational complexity theory.
Exact NP-hardness does not by itself determine approximability. Some NP-hard optimization problems possess polynomial-time approximation schemes, while others remain hard to approximate within specified ratios under additional complexity assumptions. Approximation classifications therefore require reductions that preserve objective-value relationships rather than merely yes-or-no answers.
NP-hardness likewise does not determine parameterized complexity. A problem can be NP-hard in its total input size while admitting a fixed-parameter tractable algorithm for a particular structural parameter. Conversely, a parameterized formulation may be W-hard, indicating evidence against such an algorithm even when restricted instances behave differently from the unrestricted problem.