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.
- 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
The definition of NP-hardness requires that for every problem L in NP, there exists a polynomial-time many-one reduction from L to H. An equivalent definition is that there is a polynomial-time reduction from an NP-complete problem G to H, which implies the first definition. This classification does not restrict NP-hard problems to decision problems; it also includes search problems and optimization problems.
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