Editing Many-one reduction (section)

== Karp reductions ==
A [[Polynomial-time reduction|polynomial-time]] many-one reduction from a problem ''A'' to a problem ''B'' (both of which are usually required to be [[decision problem]]s) is a polynomial-time algorithm for transforming inputs to problem ''A'' into inputs to problem ''B'', such that the transformed problem has the same output as the original problem. An instance ''x'' of problem ''A'' can be solved by applying this transformation to produce an instance ''y'' of problem ''B'', giving ''y'' as the input to an algorithm for problem ''B'', and returning its output. Polynomial-time many-one reductions may also be known as '''polynomial transformations''' or '''Karp reductions''', named after [[Richard Karp]]. A reduction of this type is denoted by <math>A \le_m^P B</math> or <math>A \le_p B</math>.<ref name="goldreich">{{citation|title=Computational Complexity: A Conceptual Perspective|first=Oded|last=Goldreich|authorlink=Oded Goldreich|publisher=Cambridge University Press|year=2008|isbn=9781139472746|pages=59–60}}</ref><ref name = "kleinberg-tardos">{{cite book | last1=Kleinberg | first1=Jon|authorlink1= Jon Kleinberg| last2=Tardos | first2=Éva|authorlink2=Éva Tardos
|year=2006
|publisher=Pearson Education
|title=Algorithm Design
|isbn=978-0-321-37291-8
|pages=452–453
}}
</ref>