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.

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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