8
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Dec 4, 2013 at 12:12
  • 3
    $\begingroup$ What's the difference to a truth table reduction? $\endgroup$
    – Markus Bläser
    Dec 4, 2013 at 12:30
  • $\begingroup$ @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? $\endgroup$
    – Sylvain
    Dec 4, 2013 at 13:24
  • $\begingroup$ 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). $\endgroup$
    – Kaveh
    Dec 4, 2013 at 13:49
  • $\begingroup$ @Sylvain Awesome Question. $\endgroup$
    – Tayfun Pay
    Mar 9, 2014 at 22:55

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.