Overview

NP-hardness is a classification used in theoretical computer science to describe problems that are at least as difficult to solve as the most challenging problems in the complexity class NP. Informally, an NP-hard problem has the property that any problem in NP can be transformed into it using an efficient (polynomial-time) procedure. The concept helps researchers distinguish tasks unlikely to admit fast, general-purpose algorithms and guides choices of methods when exact solutions are impractical. For a technical introduction see further reading.

Definition and formal idea

Formally, a decision problem H is NP-hard if every problem L in NP can be reduced to H by a polynomial-time many-one reduction. That means there is a polynomial-time computable function that maps instances of L to instances of H so that answers are preserved. NP-hardness does not require H to belong to NP; H might not even be decidable in finite time. When an NP-hard problem is also in NP it is called NP-complete, which places it among the problems both hard to solve and easy to verify.

Relationship with NP and NP-complete

The class NP consists of decision problems for which a proposed solution can be verified quickly (in polynomial time). NP-hard is a broader notion: every NP-complete problem is NP-hard, but NP-hard problems include many optimization or search problems that are not decision problems or whose solutions cannot be verified in polynomial time. The famous open question P vs NP asks whether problems in NP (and hence NP-hard problems that lie in NP) can be solved as quickly as they can be verified; this distinction drives much of modern complexity theory. See an explanation of NP-completeness here.

Typical examples

  • Boolean satisfiability (SAT) — first problem proved NP-complete, central in reductions.
  • Traveling salesman problem (optimization) — find shortest route visiting a set of cities; decision variant is NP-complete.
  • Integer programming — many formulations are NP-hard; decision variants may be NP-complete.
  • Graph coloring, clique, and partition problems — standard combinatorial problems used as benchmarks for hardness.

Practical consequences and approaches

Because NP-hard problems are believed to lack efficient general solutions, practitioners rely on alternative strategies: exact algorithms with exponential running time but feasible for small sizes, approximation algorithms that deliver provably near-optimal solutions, heuristics and local search that work well in practice, and parameterized algorithms that exploit special structure. In applied fields such as scheduling, logistics, and machine learning, recognizing NP-hardness guides realistic expectations and the selection of methods.

History and notable points

The formal study of NP-hardness and NP-completeness emerged in the early 1970s and quickly shaped modern computational complexity. Two ideas to keep in mind: NP-hardness is about relative difficulty via reductions, and it applies across decision, optimization, and search problems. Identifying a problem as NP-hard is not a proof that no fast algorithm exists, but it establishes a strong link to a wide family of challenging problems.