# NP-hardness

**NP-hardness** is a property of a computational problem: a problem is NP-hard if every problem in the complexity class NP can be reduced to it in polynomial time, so a polynomial-time algorithm for the NP-hard problem would give polynomial-time algorithms for all of NP.<sup>[1](https://www.cs.umd.edu/users/gasarch/COURSES/452/S21/notes/np.pdf)</sup> The class NP contains decision problems whose proposed solutions, or certificates, can be checked efficiently; the NP-hard problem itself need not belong to NP, and NP-hardness is a statement about relative difficulty, not about membership in any class.<sup>[1](https://www.cs.umd.edu/users/gasarch/COURSES/452/S21/notes/np.pdf)</sup><sup> • </sup><sup>[2](https://people.stfx.ca/tjsmith/lec/W26CSCI541/W26CSCI541LecHardnessCompleteness.pdf)</sup>

| Key fact | Detail |
|---|---|
| Definition | A language L is NP-hard if for every language L' in NP there is a polynomial-time (many-one) reduction from L' to L; L is NP-complete if it is NP-hard and also in NP<sup>[1](https://www.cs.umd.edu/users/gasarch/COURSES/452/S21/notes/np.pdf)</sup> |
| Origin | Stephen Cook's 1971 paper showed that any recognition problem solvable by a polynomial-time nondeterministic Turing machine reduces to propositional tautology checking; Leonid Levin independently formulated the corresponding theory in 1971<sup>[3](https://www.cs.cmu.edu/~15455/resources/Cook1971-complx-thm-proof.pdf)</sup><sup> • </sup><sup>[4](https://www.claymath.org/millennium/p-vs-np/)</sup> |
| Systematic catalog | Richard M. Karp's 1972 paper "Reducibility Among Combinatorial Problems" (Proceedings of a symposium at the IBM Thomas J. Watson Research Center, pp. 85-103, Plenum Press) reduced many combinatorial problems to known hard problems<sup>[5](https://cir.nii.ac.jp/crid/1363670320486485248)</sup> |
| Optimization vs decision | When the decision version of a combinatorial optimization problem is NP-complete, the optimization version is NP-hard; "is there a Hamiltonian cycle of length less than k" is NP-complete, while "what is the shortest tour?" is NP-hard<sup>[6](https://xlinux.nist.gov/dads/HTML/nphard.html)</sup> |
| Weak vs strong | A problem is strongly NP-hard if it remains NP-hard when its numbers are restricted to polynomially bounded values; 2-Partition and Subset Sum are weakly NP-hard, while 3-Partition, Numerical 3-Dimensional Matching, 3DM, and X3C are strongly NP-hard<sup>[7](https://ocw.mit.edu/courses/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/2c3913aefe7be0f98fcc16394ef6ea4b_MIT6_890F14_Lec2.pdf)</sup> |
| Consequence | Assuming P ≠ NP, no NP-hard problem has a polynomial-time algorithm for finding optimal solutions, and no strongly NP-hard problem has a pseudopolynomial-time algorithm<sup>[8](https://link.springer.com/article/10.1186/s13673-020-00226-w)</sup><sup> • </sup><sup>[9](https://iitg.ac.in/rinkulu/note/pseudopoly-note.pdf)</sup> |

## Definition and reductions

The standard definition uses polynomial-time many-one reductions, also called Karp reductions: a reduction from a language L to a language L' is a polynomial-time computable function f such that x is in L exactly when f(x) is in L'.<sup>[1](https://www.cs.umd.edu/users/gasarch/COURSES/452/S21/notes/np.pdf)</sup> A language is NP-hard if every language in NP reduces to it, and NP-complete if it is additionally a member of NP.<sup>[1](https://www.cs.umd.edu/users/gasarch/COURSES/452/S21/notes/np.pdf)</sup> Reductions are transitive, which is what makes the theory practical: once one natural problem is known to be NP-complete, further problems are shown hard by reducing from it rather than from an arbitrary NP machine.<sup>[1](https://www.cs.umd.edu/users/gasarch/COURSES/452/S21/notes/np.pdf)</sup>

An alternative definition via Cook, or Turing, reductions, which allow polynomially many adaptive queries to a solver, yields a different notion. Under Cook reductions, any coNP-complete language is NP-hard, since oracle access to such a language suffices to decide NP; under many-one reductions this would imply NP = coNP, which is considered unlikely.<sup>[1](https://www.cs.umd.edu/users/gasarch/COURSES/452/S21/notes/np.pdf)</sup>

NP-hardness is defined for decision problems, but it extends to optimization and search problems through their decision versions. The NIST Dictionary of Algorithms and Data Structures states the convention directly: when the decision version of a combinatorial optimization problem is NP-complete, the optimization version is NP-hard, because there is no easy way to verify that a proposed answer is optimal.<sup>[6](https://xlinux.nist.gov/dads/HTML/nphard.html)</sup>

## Origins

**Cook and Levin, 1971.** Stephen A. Cook, a computer scientist at the [University of Toronto](https://www.edgepedia.org/university-of-toronto), proved in "The Complexity of Theorem-Proving Procedures" (STOC 1971, pp. 151-158) that any recognition problem solved by a polynomial time-bounded nondeterministic [Turing machine](https://www.edgepedia.org/turing-machine) can be reduced to determining whether a given propositional formula is a tautology, and he used this notion of reducibility to define polynomial degrees of difficulty.<sup>[3](https://www.cs.cmu.edu/~15455/resources/Cook1971-complx-thm-proof.pdf)</sup> In the same year [Leonid Levin](https://www.edgepedia.org/leonid-levin) independently formulated the P versus NP problem in the Soviet Union.<sup>[4](https://www.claymath.org/millennium/p-vs-np/)</sup> The Clay Mathematics Institute lists P versus NP among its Millennium Prize Problems: if it is easy to check that a solution is correct, is it also easy to solve the problem?<sup>[4](https://www.claymath.org/millennium/p-vs-np/)</sup>

**Karp's catalog, 1972.** [Richard M. Karp](https://www.edgepedia.org/richard-m-karp)'s paper "Reducibility Among Combinatorial Problems," presented at a symposium held March 20-22, 1972 at the IBM Thomas J. Watson Research Center in Yorktown Heights, New York, and published by Plenum Press at pages 85-103, showed that a large collection of classical combinatorial problems reduces to satisfiability, establishing NP-hardness across combinatorial optimization.<sup>[5](https://cir.nii.ac.jp/crid/1363670320486485248)</sup> Luca Trevisan, a complexity theorist who has taught courses on hardness of approximation at Berkeley and Stanford, notes that the theory of [NP-completeness](https://www.edgepedia.org/np-completeness) and its success in classifying the complexity of optimization problems provided the motivation for studying efficient suboptimal algorithms.<sup>[10](https://cs.stanford.edu/people/trevisan/pcp/lecture01.pdf)</sup>

## Weak and strong NP-hardness

For problems whose inputs include numbers, hardness is measured against how those numbers are encoded. A problem is strongly NP-hard if it remains NP-hard even when the numbers are restricted to values polynomial in the input length, equivalently, even if the numbers are written in unary; it is weakly NP-hard otherwise.<sup>[7](https://ocw.mit.edu/courses/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/2c3913aefe7be0f98fcc16394ef6ea4b_MIT6_890F14_Lec2.pdf)</sup> Strong NP-hardness implies weak NP-hardness, and the distinction matters because pseudopolynomial-time algorithms, which run in time polynomial in the input length and the largest number written in unary, can exist for weakly hard problems but, unless P = NP, not for strongly hard ones.<sup>[7](https://ocw.mit.edu/courses/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/2c3913aefe7be0f98fcc16394ef6ea4b_MIT6_890F14_Lec2.pdf)</sup><sup> • </sup><sup>[9](https://iitg.ac.in/rinkulu/note/pseudopoly-note.pdf)</sup>

The canonical examples separate cleanly. 2-Partition and Subset Sum are weakly NP-hard and admit pseudopolynomial algorithms, so they are not strongly NP-hard unless P = NP; 3-Partition, Numerical 3-Dimensional Matching, 3DM, and X3C are strongly NP-hard.<sup>[7](https://ocw.mit.edu/courses/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/2c3913aefe7be0f98fcc16394ef6ea4b_MIT6_890F14_Lec2.pdf)</sup> Reductions transfer this strength: a reduction from 3-Partition rules out a pseudopolynomial algorithm for the target problem, while a reduction from Subset Sum transfers only weak hardness.<sup>[7](https://ocw.mit.edu/courses/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/2c3913aefe7be0f98fcc16394ef6ea4b_MIT6_890F14_Lec2.pdf)</sup> Multiprocessor scheduling illustrates both routes: with two processors and a target of half the total processing time the problem is at least weakly NP-hard via Partition, while with p = n/3 processors it is strongly NP-hard via 3-Partition.<sup>[7](https://ocw.mit.edu/courses/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/2c3913aefe7be0f98fcc16394ef6ea4b_MIT6_890F14_Lec2.pdf)</sup>

## Consequences and ways of coping

Hundreds of important combinatorial optimization problems are NP-hard, so no worst-case efficient exact algorithm is expected for any of them unless P = NP.<sup>[10](https://cs.stanford.edu/people/trevisan/pcp/lecture01.pdf)</sup> Trevisan's lecture notes list the standard relaxations of the requirement of an optimal polynomial-time algorithm on all inputs: algorithms that run in gently exponential time such as \( O(1.1^n) \), which can be practical on small instances; algorithms that run in polynomial time on typical instances; and approximation algorithms that find solutions whose cost or value is close to the optimum.<sup>[10](https://cs.stanford.edu/people/trevisan/pcp/lecture01.pdf)</sup>

**Parameterized complexity.** [Parameterized complexity](https://www.edgepedia.org/parameterized-complexity) analyzes instances by an input length n and a numerical parameter k, calling a problem fixed-parameter tractable (FPT) if it can be solved in \( f(k) \cdot n^{O(1)} \) time for an arbitrary computable f independent of n; a running time of \( 2^{O(k)} \cdot n^{3} \) counts as tractable in this setting, while \( n^{O(k)} \) does not.<sup>[11](https://www.sciencedirect.com/science/article/pii/S0305048317304152)</sup> The approach exploits the fact that many natural parameters, such as the number of jobs or the size of a solution, are small in practice even when the total input is large.<sup>[11](https://www.sciencedirect.com/science/article/pii/S0305048317304152)</sup> The framework also grades hardness within NP: Weighted 3-SAT, Clique, and Independent Set are W[1]-hard, and Dominating Set, Weighted CNF-SAT, and Set Cover are W[2]-hard, meaning these problems are unlikely to admit FPT algorithms under those parameterizations.<sup>[8](https://link.springer.com/article/10.1186/s13673-020-00226-w)</sup>

**Approximation and hardness of approximation.** For NP-hard optimization problems, a polynomial-time approximation algorithm trades optimality for a provable guarantee on solution quality. Hardness of approximation, one of the most active subfields of complexity theory, establishes which problems admit such algorithms under reasonable hardness assumptions; for many problems, matching lower and upper bounds on polynomial-time approximability have been shown, proving that simple algorithms such as the Goemans-Williamson algorithm or random sampling achieve best-possible approximation ratios.<sup>[12](https://www.dm.uni-bonn.de/lectures/ss25/selected_topics_algorithms_and_optimization.html)</sup> Almost all inapproximability results are proved using the PCP Theorem and its variants, one of the deepest theorems in computational complexity, and the results are typically conditional on P ≠ NP, a necessary assumption since all combinatorial optimization problems become tractable if P = NP.<sup>[13](https://theory.stanford.edu/~trevisan/pcp/)</sup> Representative tight results include a 7/8-inapproximability for Max E3SAT obtained by reduction,<sup>[14](https://courses.csail.mit.edu/6.890/fall14/lectures/L12.html)</sup> Håstad's tight inapproximability theorems for some MaxCSPs,<sup>[12](https://www.dm.uni-bonn.de/lectures/ss25/selected_topics_algorithms_and_optimization.html)</sup> and tight inapproximability of Max-Cut up to the Goemans-Williamson threshold under the Unique Games Conjecture.<sup>[12](https://www.dm.uni-bonn.de/lectures/ss25/selected_topics_algorithms_and_optimization.html)</sup>

**Exact exponential and heuristic methods.** Every problem in NP can be solved in exponential time by exhaustive search, and a research area studies improved worst-case bounds for NP-hard problems, with early examples including an \( O^*(1.4422^n) \) algorithm for deciding 3-colorability of an n-vertex graph by Lawler and an \( O^*(1.2599^n) \) algorithm for maximum independent set by Tarjan and Trojanowski.<sup>[15](https://doi.org/10.1016%2Fj.dam.2007.03.023)</sup> In applications such as scheduling, where most problems of practical interest are NP-hard, this complexity motivates exact methods such as branch-and-bound and integer programming for smaller instances and heuristic and metaheuristic methods for larger real-world instances.<sup>[16](https://technav.ieee.org/topic/optimal-scheduling/)</sup> SAT solvers illustrate that worst-case hardness and practical behavior can diverge: state-of-the-art satisfiability solvers handle real-world instances with millions of variables, often in close to linear time, while tiny formulas with a few hundred variables can remain beyond reach.<sup>[17](https://siglog.hosting.acm.org/wp-content/uploads/2015/10/siglog_news_5.pdf)</sup>

## NP-hard versus NP-complete

The two labels are often confused. NP-complete problems are exactly the NP-hard problems that also lie in NP, meaning their yes-answers have short, efficiently checkable certificates.<sup>[1](https://www.cs.umd.edu/users/gasarch/COURSES/452/S21/notes/np.pdf)</sup> An NP-hard problem can fail to be NP-complete either because it is not a decision problem, as with optimization versions of NP-complete decision problems, or because membership in NP is unknown or false.<sup>[6](https://xlinux.nist.gov/dads/HTML/nphard.html)</sup> The distinction has practical weight: if one NP-complete problem has a polynomial-time algorithm then every problem in NP does, so the NP-complete problems stand or fall together, while NP-hardness alone only asserts that the problem is at least as difficult as everything in NP.<sup>[1](https://www.cs.umd.edu/users/gasarch/COURSES/452/S21/notes/np.pdf)</sup>

## References

1. [NP Completeness lecture notes, William Gasarch, University of Maryland CMSC 452](https://www.cs.umd.edu/users/gasarch/COURSES/452/S21/notes/np.pdf)
2. [Lecture 5, CSCI 541 Theory of Computing, St. Francis Xavier University](https://people.stfx.ca/tjsmith/lec/W26CSCI541/W26CSCI541LecHardnessCompleteness.pdf)
3. [Stephen A. Cook (1971). The Complexity of Theorem-Proving Procedures (transliteration), Carnegie Mellon University](https://www.cs.cmu.edu/~15455/resources/Cook1971-complx-thm-proof.pdf)
4. [P vs NP, Clay Mathematics Institute Millennium Problems](https://www.claymath.org/millennium/p-vs-np/)
5. [Richard M. Karp (1972). Reducibility Among Combinatorial Problems, CiNii Research record](https://cir.nii.ac.jp/crid/1363670320486485248)
6. [NP-hard, Dictionary of Algorithms and Data Structures, NIST](https://xlinux.nist.gov/dads/HTML/nphard.html)
7. [Lecture 2 scribe notes, MIT 6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs, Fall 2014](https://ocw.mit.edu/courses/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/2c3913aefe7be0f98fcc16394ef6ea4b_MIT6_890F14_Lec2.pdf)
8. [Li, W. et al. (2020). Parameterized algorithms of fundamental NP-hard problems: a survey, Human-centric Computing and Information Sciences](https://link.springer.com/article/10.1186/s13673-020-00226-w)
9. [NP-hardness and pseudo-polynomial time algorithms, IIT Guwahati lecture note](https://iitg.ac.in/rinkulu/note/pseudopoly-note.pdf)
10. [Luca Trevisan. Notes for Lecture 1, CS294: PCP and Hardness of Approximation, UC Berkeley](https://cs.stanford.edu/people/trevisan/pcp/lecture01.pdf)
11. [Scheduling two agents on a single machine: a parameterized analysis of NP-hard problems, ScienceDirect](https://www.sciencedirect.com/science/article/pii/S0305048317304152)
12. [Hardness of Approximation, Research Institute for Discrete Mathematics, University of Bonn, Summer 2025](https://www.dm.uni-bonn.de/lectures/ss25/selected_topics_algorithms_and_optimization.html)
13. [CS 294: PCP and Hardness of Approximation, Luca Trevisan, Stanford](https://theory.stanford.edu/~trevisan/pcp/)
14. [MIT 6.890 Lecture 12 notes](https://courses.csail.mit.edu/6.890/fall14/lectures/L12.html)
15. [Open problems around exact algorithms, Discrete Applied Mathematics](https://doi.org/10.1016%2Fj.dam.2007.03.023)
16. [Optimal scheduling, IEEE Technology Navigator](https://technav.ieee.org/topic/optimal-scheduling/)
17. [A (Biased) Proof Complexity Survey for SAT Practitioners, ACM SIGLOG News](https://siglog.hosting.acm.org/wp-content/uploads/2015/10/siglog_news_5.pdf)

---
*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods › Computational complexity › Reducibility, hardness, and completeness*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license