Computer science Computational complexity: resources and classes Concept
NP-hardness
Summary
A problem is NP-hard when every problem in NP reduces to it by a polynomial-time reduction. An NP-hard problem is at least as hard as every problem in NP. A polynomial-time algorithm for one NP-hard problem would give one for all of NP, and so would prove that P equals NP. NP-hard problems need not lie in NP; some, such as the halting problem, are not even decidable.
Where this leads
18 pages build on this one.
- Cutting stock problem
- Christofides algorithm
- Pursuit–evasion
- Bin packing problem
- Goemans–Williamson algorithm
- HP lattice model of proteins
- Facility location problem
- Quadratic assignment problem
- Lin–Kernighan heuristic
- NP-hardness of integer programming
- NP-completeness
- Unique games conjecture
- Flow-shop scheduling
- Logic optimization
- Vehicle routing problem
- Johnson's rule
- Travelling salesman problem
- Held–Karp algorithm
Further reading
About this page
| Tag | MHA48AWBXN |
|---|---|
| URI | m2://MHA48AWBXN |
| Kind | concept |
| Writing | W0 stub |
| MSC | 68Q17, 68Q15 |
| Same as | |
| Changed | 3 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
Used by
- Pursuit–evasion
- Bin packing problem
- HP lattice model of proteins
- Facility location problem
- Quadratic assignment problem
- NP-hardness of integer programming
- NP-completeness
- Unique games conjecture
- Flow-shop scheduling
- Logic optimization
- Vehicle routing problem
- Travelling salesman problem