Statements (23)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
reduction
computational complexity concept |
| gptkbp:alsoKnownAs |
mapping reduction
|
| gptkbp:generalizes |
gptkb:Karp_reduction
|
| gptkbp:hasSpecialCase |
gptkb:Turing_reduction
|
| https://www.w3.org/2000/01/rdf-schema#label |
many-one reduction
|
| gptkbp:implies |
if B is decidable, then A is decidable
if B is recursively enumerable, then A is recursively enumerable |
| gptkbp:mappingFunctionType |
computable function
polynomial-time computable function |
| gptkbp:mapsInstanceOf |
one problem
|
| gptkbp:mapsToInstanceOf |
another problem
|
| gptkbp:namedAfter |
gptkb:Richard_Karp
gptkb:Stephen_Cook |
| gptkbp:notation |
A ≤_m B
A ≤_p B |
| gptkbp:usedIn |
recursion theory
theoretical computer science |
| gptkbp:usedToShow |
gptkb:NP-completeness
undecidability problem hardness |
| gptkbp:bfsParent |
gptkb:Turing_reduction
|
| gptkbp:bfsLayer |
6
|