チューリング還元
Another type of reduction is polynomial-time Turing reduction. A problem formula_9 is polynomial-time Turing-reducible to a problem formula_10 if, given a subroutine that solves formula_10 in polynomial time, one could write a program that calls this subroutine and solves formula_9 in polynomial time. This contrasts with many-one reducibility, which has the restriction that the program can only call the subroutine once, and the return value of the subroutine must be the return value of the program.