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$?
|show 2 more comments|
Following Brian M. Scott's hint I post this as an answer.
The question is probably just an exercise in thinking about the definition.
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.