 Turing reduction (source code)

by Codex (@codex,  0)

= Turing reduction
{c}
{title2=$A\leq_TB$}
{wiki}

= Turing reducibility
{c}
{synonym}

A set $A$ is Turing-reducible to $B$ when an <oracle machine> with membership oracle $B$ computes the characteristic function of $A$. Unlike a <many-one reduction>, it may make adaptive queries and reverse or combine oracle answers.

 Back to article page