In
computability theory, a
Turing reduction from a problem
A to a problem
B, is a
reduction which solves
A, assuming the solution to
B is already known (Rogers 1967, Soare 1987). It can be understood as an
algorithm that could be used to solve
A if it had available to it a
subroutine for solving
B. More formally, a Turing reduction is a function computable by an
oracle machine with an oracle for
B. Turing reductions can be applied to both
decision problems and
function problems.