Karp reductions
E519560
concept in computational complexity theory
polynomial-time many-one reduction
reduction between decision problems
Karp reductions are polynomial-time many-one reductions used in computational complexity theory to show that one decision problem is at least as hard as another, central to defining NP-completeness.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| Karp reduction | 0 |
Statements (50)
| Predicate | Object |
|---|---|
| instanceOf |
concept in computational complexity theory
ⓘ
polynomial-time many-one reduction ⓘ reduction between decision problems ⓘ |
| alsoKnownAs |
P-time many-one reduction
ⓘ
polynomial-time many-one reduction ⓘ |
| assumptionOnEncoding | instances are encoded as finite strings over a fixed alphabet ⓘ |
| canonicalExampleFrom | SAT NERFINISHED ⓘ |
| canonicalExampleTo |
CLIQUE
ⓘ
HAMILTONIAN CYCLE NERFINISHED ⓘ VERTEX COVER ⓘ |
| category | many-one reduction ⓘ |
| closureProperty | transitive ⓘ |
| codomain | decision problem ⓘ |
| complexityClassContext |
NP
NERFINISHED
ⓘ
NP-complete ⓘ P ⓘ |
| computabilityRequirement | reduction function must be computable in polynomial time ⓘ |
| contrastWith |
Cook reduction
ⓘ
Turing reduction NERFINISHED ⓘ |
| domain | decision problem ⓘ |
| ensuresProperty | if B is in P and A ≤_m^P B then A is in P ⓘ |
| field | computational complexity theory ⓘ |
| formalDefinition | a function f from instances of problem A to instances of problem B such that x is in A if and only if f(x) is in B and f is computable in polynomial time ⓘ |
| impliesHardness | if A Karp-reduces to B and A is NP-hard then B is NP-hard ⓘ |
| importance | standard notion of reduction for NP-completeness proofs ⓘ |
| influencedBy | earlier notions of reducibility in recursion theory ⓘ |
| introducedBy | Richard M. Karp NERFINISHED ⓘ |
| introducedInWork | "Reducibility Among Combinatorial Problems" NERFINISHED ⓘ |
| introducedInYear | 1972 ⓘ |
| logicalForm | single call transformation from one instance to another ⓘ |
| mappingType | many-one reduction ⓘ |
| namedAfter | Richard M. Karp NERFINISHED ⓘ |
| NPCompleteDefinitionRole | a problem is NP-complete if it is in NP and every problem in NP Karp-reduces to it ⓘ |
| preservesMembership | x ∈ A iff f(x) ∈ B ⓘ |
| problemType | decision problems with yes/no answers ⓘ |
| relatedConcept |
Cook–Levin theorem
NERFINISHED
ⓘ
complete problems for NP ⓘ polynomial-time reduction ⓘ |
| relationToNPCompleteness | used to define NP-complete problems ⓘ |
| requires | polynomially bounded output size ⓘ |
| strongerThan | polynomial-time Turing reduction in terms of restriction ⓘ |
| symbolicNotation | ≤_m^P ⓘ |
| timeComplexityConstraint | polynomial time ⓘ |
| transitivityDescription | if A ≤_m^P B and B ≤_m^P C then A ≤_m^P C ⓘ |
| usedFor |
comparing hardness of decision problems
ⓘ
proving NP-completeness ⓘ showing one problem is at least as hard as another ⓘ |
| usedIn |
classification of NP-complete problems
ⓘ
reductions between SAT and other problems ⓘ |
| usedToShow | NP-hardness of optimization problems via decision versions ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.