NP-hardness
E512971
NP-hardness is a classification in computational complexity theory for problems at least as hard as the hardest problems in NP, such that every problem in NP can be reduced to them in polynomial time.
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf | computational complexity theory concept ⓘ |
| appliesTo | decision versions of optimization problems ⓘ |
| assumes | polynomial-time computability of reductions ⓘ |
| characterization | at least as hard as every problem in NP ⓘ |
| closureProperty | closed under polynomial-time reductions ⓘ |
| complexityStatus | captures worst-case difficulty relative to NP ⓘ |
| consequence |
if any NP-hard problem is in P then P = NP
ⓘ
polynomial-time algorithm for one NP-complete problem yields polynomial-time algorithms for all NP problems ⓘ |
| definedOver |
decision problems
ⓘ
optimization problems ⓘ search problems ⓘ |
| distinguishedFrom |
NP-completeness
NERFINISHED
ⓘ
NP-easiness ⓘ co-NP-hardness ⓘ |
| doesNotRequire | membership in NP ⓘ |
| exampleProblem |
3-SAT is NP-hard
NERFINISHED
ⓘ
clique problem (optimization version) is NP-hard ⓘ halting problem (under suitable reductions) NERFINISHED ⓘ satisfiability problem for Boolean formulas (SAT) is NP-hard ⓘ subset sum optimization problem is NP-hard ⓘ traveling salesman problem (optimization version) is NP-hard NERFINISHED ⓘ vertex cover problem (optimization version) is NP-hard ⓘ |
| field |
computational complexity theory
NERFINISHED
ⓘ
theoretical computer science ⓘ |
| formalDefinition | a problem H is NP-hard if for every problem L in NP, L ≤p H ⓘ |
| generalizationOf | NP-completeness ⓘ |
| historicalWork |
Cook–Levin theorem
NERFINISHED
ⓘ
Karp's 21 NP-complete problems paper (1972) NERFINISHED ⓘ |
| implies | problem is at least as hard as NP-complete problems ⓘ |
| introducedBy |
Richard Karp
NERFINISHED
ⓘ
Stephen Cook NERFINISHED ⓘ |
| keyCondition | every problem in NP reduces to the problem in polynomial time ⓘ |
| reductionType |
polynomial-time Turing reduction
ⓘ
polynomial-time many-one reduction ⓘ |
| relatedClass |
EXPTIME
ⓘ
NP NERFINISHED ⓘ NP-completeness ⓘ PSPACE ⓘ co-NP NERFINISHED ⓘ |
| subsetRelation |
NP-complete problems are NP-hard and in NP
ⓘ
NP-hard problems may lie outside NP ⓘ |
| typicalAssumption | P ≠ NP implies no polynomial-time algorithm for NP-hard problems ⓘ |
| typicalUseContext | reductions in hardness proofs ⓘ |
| usedFor |
classifying computational intractability
ⓘ
proving non-existence of efficient algorithms unless P = NP ⓘ |
| variant |
strong NP-hardness
ⓘ
weak NP-hardness ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.