<p>I'm pretty sure you can find this in the book <a href="http://www.springer.com/birkhauser/computer+science/book/978-0-8176-3966-2" rel="nofollow">Bounded Queries in Recursion Theory</a> by Martin and Gasarch, but I don't have access to a copy now to check. </p>

<p>(Your statement gives an upper bound of $2^f$; most of that book is about lower bounding such quantities, so the upper bound must be in there somewhere, probably very near the beginning.)</p>

<p>PS - I agree with M. Blaser's comment: you're basically talking about truth-table reductions without using that terminology.</p>

CC BY-SA 3.0
2013-12-04T19:20:06.110Z
2013-12-04T19:20:06.110Z
Joshua Grochow
<p>I am looking for a reference on `reducing' Turing reductions to many-one reductions.  I have in mind a statement of the following form (similar enough statements would also satisfy me):</p>

<p><strong>Theorem.</strong>  If $\mathsf{A}\leq_T^f \mathsf{B}$, then $\mathsf A\leq_m^{2^f}\mathsf B^{tt}$.</p>

<p>where "$\leq_T^f$" and "$\leq_m^f$" denote respectively Turing and many-one reductions in deterministic time $f(n)$, and "$\mathsf{B}^{tt}$" denotes a `truth table' variant of the language $\mathsf{B}$, which evaluates a Boolean combination of checks "$x\in\mathsf{B}$".</p>

<p><em>Proof idea for the statement:</em>  Simulate the $f(n)$-time bounded oracle Turing machine used in the Turing reduction: it's easy enough to obtain a nondeterministic Turing transducer also in time $f(n)$ that guesses the answers of the $\mathsf B$ oracle and writes a conjunction of checks "$x\in\mathsf B$" or "$x\not\in\mathsf{B}$" on the output, to be evaluated by an $\mathsf B^{tt}$ machine.  This transducer can be determinized by exploring both outcomes of the oracle calls, and handling them through disjunctions in the output; it now works in time $2^{f(n)}$.</p>

<p>Oddly enough, I cannot seem to find any related result in complexity textbooks.</p>

<p>Edit: renamed "$A\mathsf B$" into "$\mathsf B^{tt}$" to emphasize the relation with truth tables, as pointed out by @MarkusBläser.</p>

CC BY-SA 3.0
2013-12-04T12:12:22.187Z
Interesting. To put it differently, you first reduce it to the problem of checking if any computation of length $f(|x|)$ of the reduction machine with oracle $B$ accepts, and then reduce that to $AB$ by considering all accepting branches (considering all possible values of membership in $B$ queries) and asking in a single query to $AB$ if any of them is correct. The obvious place to check is Classical Recursion Theory, it discusses various reductions and their relations extensively, but I don't remember seeing anything similar.
Kaveh
CC BY-SA 3.0
2013-12-04T12:30:27.990Z
What's the difference to a truth table reduction?
Markus Bläser
CC BY-SA 3.0
2013-12-04T13:24:32.593Z
@MarkusBläser: Not much, the many-one reduction $\mathsf A\leq^{2^f}_mA\mathsf B$ could (I think) also be seen as a truth table reduction $\mathsf A\leq_{tt}^{2^f}\mathsf B$. Any references for this variant of the theorem?
Sylvain
CC BY-SA 3.0
2013-12-04T13:49:14.093Z
ps: if you don't get an answer here you might want to repost this on MO, there are a number of computability theorists on MO that don't visit cstheory (at least not very often).
Kaveh
CC BY-SA 3.0
2014-03-09T22:55:40.533Z
@Sylvain Awesome Question.
Tayfun Pay
<cc.complexity-theory><reference-request><complexity-classes>
Reference for Turing to many-one reductions
Sylvain
# Reference for Turing to many-one reductions

(Asked by: username_0 on 2013-12-04)

I am looking for a reference on `reducing' Turing reductions to many-one reductions. I have in mind a statement of the following form (similar enough statements would also satisfy me):

**Theorem.** If $\mathsf{A}\leq\_T^f \mathsf{B}$, then $\mathsf A\leq\_m^{2^f}\mathsf B^{tt}$.

where "$\leq\_T^f$" and "$\leq\_m^f$" denote respectively Turing and many-one reductions in deterministic time $f(n)$, and "$\mathsf{B}^{tt}$" denotes a `truth table' variant of the language $\mathsf{B}$, which evaluates a Boolean combination of checks "$x\in\mathsf{B}$".

*Proof idea for the statement:* Simulate the $f(n)$-time bounded oracle Turing machine used in the Turing reduction: it's easy enough to obtain a nondeterministic Turing transducer also in time $f(n)$ that guesses the answers of the $\mathsf B$ oracle and writes a conjunction of checks "$x\in\mathsf B$" or "$x\not\in\mathsf{B}$" on the output, to be evaluated by an $\mathsf B^{tt}$ machine. This transducer can be determinized by exploring both outcomes of the oracle calls, and handling them through disjunctions in the output; it now works in time $2^{f(n)}$.

Oddly enough, I cannot seem to find any related result in complexity textbooks.

Edit: renamed "$A\mathsf B$" into "$\mathsf B^{tt}$" to emphasize the relation with truth tables, as pointed out by @MarkusBläser.

**Tags:** cc.complexity-theory, reference-request, complexity-classes
> **Comments:**
> **username_1**: Interesting. To put it differently, you first reduce it to the problem of checking if any computation of length $f(|x|)$ of the reduction machine with oracle $B$ accepts, and then reduce that to $AB$ by considering all accepting branches (considering all possible values of membership in $B$ queries) and asking in a single query to $AB$ if any of them is correct. The obvious place to check is Classical Recursion Theory, it discusses various reductions and their relations extensively, but I don't remember seeing anything similar.  
> **username_2**: What's the difference to a truth table reduction?  
> **username_0**: @MarkusBläser: Not much, the many-one reduction $\mathsf A\leq^{2^f}_mA\mathsf B$ could (I think) also be seen as a truth table reduction $\mathsf A\leq_{tt}^{2^f}\mathsf B$. Any references for this variant of the theorem?  
> **username_1**: ps: if you don't get an answer here you might want to repost this on MO, there are a number of computability theorists on MO that don't visit cstheory (at least not very often).  
> **username_3**: @Sylvain Awesome Question.  

---

## 1 answers

### Answer by username_4 on 2013-12-04. Score: 2

I'm pretty sure you can find this in the book [Bounded Queries in Recursion Theory](http://www.springer.com/birkhauser/computer+science/book/978-0-8176-3966-2) by Martin and Gasarch, but I don't have access to a copy now to check.

(Your statement gives an upper bound of $2^f$; most of that book is about lower bounding such quantities, so the upper bound must be in there somewhere, probably very near the beginning.)

PS - I agree with M. Blaser's comment: you're basically talking about truth-table reductions without using that terminology.


---

