Turing reduction
nounEtymology After Alan Turing.
1
Computing, Computing theory, Engineering, Mathematics, Natural sciences, Physical sciences, Sciences A reduction that solves a problem if the solution to another problem is already known, i.e. an algorithm that could be used to solve A if it had available to it a subroutine for solving B.
- Related terms
- Cook reduction, oracle machine