polynomial-time many-one reduction

GPTKB entity

Statements (17)
Predicate Object
gptkbp:instanceOf reduction
computational complexity concept
gptkbp:alsoKnownAs gptkb:Karp_reduction
https://www.w3.org/2000/01/rdf-schema#label polynomial-time many-one reduction
gptkbp:implies if problem A reduces to problem B and B is in P, then A is in P
gptkbp:mappingFunction computable in polynomial time
gptkbp:mapType instances of one decision problem to another
gptkbp:namedAfter gptkb:Richard_Karp
gptkbp:preserves membership in the language
gptkbp:symbol ≤_m^P
gptkbp:type gptkb:many-one_reduction
polynomial-time reduction
gptkbp:usedIn theoretical computer science
gptkbp:usedToDefine gptkb:NP-completeness
gptkbp:bfsParent gptkb:Levin_reduction
gptkb:co-NP-complete
gptkbp:bfsLayer 6