= Polynomial-time Turing reduction
A <polynomial-time Turing reduction> from a <decision problem> $A$ to a <decision problem> $B$ is a <deterministic algorithm> deciding membership in $A$ in <polynomial time> when allowed to query whether <string>[strings] belong to $B$. An <oracle Turing machine> models each query answer as a single oracle operation, while writing the query and using the answer still costs time. Queries may depend on earlier answers.
For example, the complement of $B$ reduces to $B$ by asking one membership question and reversing its answer. This is a Turing reduction, regardless of whether there is a simple many-one reduction with the same effect. A <polynomial-time many-one reduction> instead computes one transformed instance whose answer is used unchanged.
If $A$ reduces to $B$ this way and $B$ has a <polynomial-time algorithm>, then $A$ does too: substitute that <algorithm> at each oracle call. <polynomial>[Polynomially] many queries of <polynomial> length keep the total cost <polynomial>. Completeness claims must specify which reduction is intended because adaptive access is more permissive.
Back to article page
