チューリング還元
A polynomial-time Turing reduction from a problem "A" to a problem "B" is an algorithm that solves problem "A" using a polynomial number of calls to a subroutine for problem "B", and polynomial time outside of those subroutine calls. Polynomial-time Turing reductions are also known as Cook reductions, named after Stephen Cook. A reduction of this type may be denoted by the expression formula_4. Many-one reductions can be regarded as restricted variants of Turing reductions where the number of calls made to the subroutine for problem "B" is exactly one and the value returned by the reduction is the same value as the one returned by the subroutine.