Editing Polynomial-time reduction (section)

{{Short description|Method for solving one problem using another}}

In [[computational complexity theory]], a '''polynomial-time reduction''' is a method for solving one problem using another. One shows that if a hypothetical [[subroutine]] solving the second problem exists, then the first problem can be solved by transforming or [[Reduction (complexity)|reducing]] it to inputs for the second problem and calling the subroutine one or more times. If both the time required to transform the first problem to the second, and the number of times the subroutine is called is [[polynomial]], then the first problem is polynomial-time reducible to the second.<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>

A polynomial-time reduction proves that the first problem is no more difficult than the second one, because whenever an efficient [[algorithm]] exists for the second problem, one exists for the first problem as well. By [[contraposition]], if no efficient algorithm exists for the first problem, none exists for the second either.<ref name = "kleinberg-tardos"/> Polynomial-time reductions are frequently used in complexity theory for defining both [[complexity class]]es and [[complete problem]]s for those classes.