# Reference for Turing to many-one reductions

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.

• 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 Dec 4 '13 at 12:12
• What's the difference to a truth table reduction? – Markus Bläser Dec 4 '13 at 12:30
• @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 Dec 4 '13 at 13:24
• 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 Dec 4 '13 at 13:49
• @Sylvain Awesome Question. – Tayfun Pay Mar 9 '14 at 22:55

## 1 Answer

I'm pretty sure you can find this in the book Bounded Queries in Recursion Theory 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.