NP-hardness
Problems at least as hard as the hardest in NP.
NP-hardness is a classification in computational complexity theory for computational problems that are at least as hard to solve as the hardest problems in the complexity class NP. A problem H is called NP-hard if every problem L in NP can be reduced to H in polynomial time, meaning that a fast solution for H would yield fast solutions for all NP problems. This concept is central to understanding the limits of efficient computation, as it is suspected but unproven that P≠NP, making polynomial-time algorithms for NP-hard problems unlikely.
A decision problem qualifies as NP-hard when, for every problem in NP, there exists a polynomial-time many-one reduction from that problem to it. An equivalent definition requires a polynomial-time reduction from any NP-complete problem to H, since every NP problem reduces to that NP-complete problem. This broader definition also encompasses search and optimization problems, not just decision problems. If P does not equal NP, then no NP-hard problem can be solved in polynomial time. However, some NP-hard optimization problems can be approximated to a constant ratio (those in APX) or to any desired ratio (those in PTAS or FPTAS). All NP-complete problems are NP-hard; for instance, the traveling salesman problem (finding the least-cost cyclic route through all nodes of a weighted graph) and the subset sum problem (determining whether a non-empty subset of integers sums to zero) are NP-hard. The subset sum problem is also NP-complete. Some NP-hard problems are not NP-complete, such as the halting problem, which asks whether a given program and input will run forever. The halting problem is undecidable, yet it is NP-hard because any NP problem can be reduced to it; for example, Boolean satisfiability can be transformed into a Turing machine that halts only upon finding a satisfying assignment. Since all NP problems are decidable in finite time, the halting problem cannot be in NP. Other NP-hard problems are decidable but neither NP-complete nor undecidable, such as the language of true quantified Boolean formulas, which is decidable in polynomial space but not in non-deterministic polynomial time unless NP equals PSPACE. NP-hard problems do not need to belong to the class NP; they may even be undecidable. They are often tackled using rules-based languages in fields such as cryptography, data mining, scheduling, routing, and pl
- field
- Computational complexity theory
- known_for
- Defining problems at least as hard as the hardest problems in NP
- related_classes
- NP, NP-complete, NP-easy, NP-equivalent, NP-intermediate
- key_consequence
- If P≠NP, NP-hard problems cannot be solved in polynomial time
Lore & Background
NP-hardness is a classification in computational complexity theory for problems that are at least as difficult to solve as the hardest problems in the complexity class NP. Formally, a problem H is NP-hard if every problem L in NP can be transformed into H via a polynomial-time reduction, meaning that an efficient solution for H would immediately yield an efficient solution for any NP problem. An equivalent definition requires a polynomial-time reduction from any NP-complete problem to H, which automatically satisfies the first condition. This classification is not limited to decision problems; it also applies to search problems and optimization problems. A simple example is the subset sum problem. All NP-complete problems are NP-hard, but some NP-hard problems are not NP-complete. For instance, the halting problem—asking whether a given program will run forever—is NP-hard but not NP-complete, because it is undecidable and therefore not in NP. Other NP-hard problems are decidable but not NP-complete, such as the language of true quantified Boolean formulas, which is decidable in polynomial space. If P ≠ NP, no NP-hard problem can be solved in polynomial time. However, some NP-hard optimization problems can be approximated within a constant ratio, or even any desired ratio, as seen in classes like APX, PTAS, and FPTAS. NP-hard problems appear in areas such as cryptography, scheduling, routing, data mining, and configuration.
Reader's Guide
NP-hardness is significant because it identifies problems that are believed to be intractable—if P≠NP, no polynomial-time algorithm exists for any NP-hard problem. However, some NP-hard optimization problems can be approximated in polynomial time up to a constant ratio (those in APX) or any ratio (those in PTAS or FPTAS). The concept also distinguishes between NP-hard problems that are NP-complete (and thus in NP) and those that are not, such as the undecidable halting problem. NP-hard problems appear in many application areas including cryptography, scheduling, routing, and data mining, and are often tackled with rules-based languages or approximation methods.
Did You Know?
- All NP-complete problems are also NP-hard.
- The halting problem is not NP-hard under polynomial-time many-one reductions because such reductions are defined only for decidable problems, and the halting problem is undecidable.
- NP-hard problems do not have to be elements of the complexity class NP; they may not even be decidable.
- The subset sum problem is a simple example of an NP-hard problem.
Frequently Asked Questions
Who is NP-hardness?
NP-hardness is a classification label in computational complexity theory that marks a problem as being at least as difficult as the toughest challenges within the NP class. It does not require the problem itself to belong to NP—only that every NP problem can be efficiently transformed into it.
What are NP-hardness's powers or role?
Its defining power is that a polynomial-time algorithm for any single NP-hard problem would immediately yield polynomial-time solutions for every problem in NP. This makes it the ultimate 'crack one, crack them all' benchmark in the field.
How does NP-hardness's story end?
The central open question is whether P equals NP; if it does not (as most researchers suspect), no NP-hard problem admits a polynomial-time algorithm. The 'ending' therefore remains unresolved, and NP-hardness stands as a permanent wall against efficient exact solutions.
Why is NP-hardness important?
It draws the practical boundary of what we should expect to solve efficiently, steering researchers toward approximations, heuristics, or special-case algorithms rather than futile searches for brute-force exact methods. Without this label, we would lack a principled way to declare a problem beyond the reach of fast computation.
What's the difference between NP-hard and NP-complete?
NP-complete problems sit inside NP and are also NP-hard, whereas NP-hard problems need not be in NP at all (the halting problem is a classic example). Think of NP-complete as the intersection: in NP AND at least as hard as everything in NP.
More in Complexity Theory 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record