# Truth table reduction

I'm learning algorithm theory and the teacher asked a question that confuses me.

Do $A$ and $B$ exist such that $A$ is not truth-table reducible to $B$, but $B$ is truth-table reducible to $A$?

-
@Martins I have edited your question for grammar - please check that the meaning is the same as what you intended. Thanks. – Chris Taylor May 15 '12 at 9:56
I just read the definition of reduction on wp en.wikipedia.org/wiki/Reduction_%28complexity%29 It seems to me that the question needs some additional information. So $A$, $B\subset \mathbb N$? What is the set of functions $F$? – Simon Markett May 15 '12 at 10:40
Take an undecidable problem $A$, like the decision problem for Peano Arithmetic ($A$ is a subset of the integers consisting of Gödel codes of true sentences in PA), and a decidable one $B$, like the set of all natural numbers, or the empty set. Then your truth-table reduction from $B$ to $A$ may ask $0=0$ or $0=1$ to the oracle for $A$, depending on what $B$ you picked, and the decision just be equal to what the oracle says -you could do the opposite, switch 0s and 1s appropriately. But a truth-table reduction (or Turing reduction) from $A$ to $B$ would imply that $A$ is decidable. – plm May 15 '12 at 11:07
@Simon: No additional information is needed: the term truth-table reduction fully specifies the kind of reduction. – Brian M. Scott May 15 '12 at 18:08
@Brian: Good to know. In the end I have no idea of this field and just wanted to make a comment along the lines "it would be helpful to give some background information". Looks like this time the joke's on me. – Simon Markett May 15 '12 at 18:16

Take $A$ an undecidable language on an alphabet with $n$ elements (assume it does not contain $\epsilon$ the empty word), or the corresponding subset of $\mathbb N$ by interpreting words as $n$-ary expansions. $A$ may be formulas provable with Peano's axioms for arithmetic. In this case Gödel numbering of formulas gives a second way of viewing $A$ as a set of natural numbers. Gödel and Turing proved $A$ is not decidable: there is no Turing machine that stops for all input (word in the alphabet $A$ is encoded in) with the right answer, 1 if the input is in $A$ and 0 if not. (Remark: The language is recursively enumerable so there is a TM which accepts all and only words in $A$, but then it will not stop on some input -which therefore is not in $A$, but this machine will not tell.)
Take $B$ a decidable language, for instance all nonempty words, or the empty set.
Now $B$ truth-table-reduces to $A$ simply outputing the easily-computed (without calling on the oracle) answer, i.e. always accepting in the first example of $B$ above. But $A$ does not so reduce to $B$ because truth-table calls to computable oracles can be implemented as Turing machines, by adding the TM working to output oracle answers for $B$ and the truth-table call procedure, to a putative TM deciding $A$ with $B$ as oracle. This would give a TM deciding $A$, and we know this is impossible.