2
$\begingroup$

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$?

  • 0
    @Martins I have edited your question for grammar - please check that the meaning is the same as what you intended. Thanks.2012-05-15
  • 0
    I just read the definition of reduction on wp http://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$?2012-05-15
  • 0
    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.2012-05-15
  • 1
    @Simon: No additional information is needed: the term *truth-table reduction* fully specifies the kind of reduction.2012-05-15
  • 0
    @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.2012-05-15
  • 0
    In my previous comment I used a call to an undecidable langauge $A$. But actually any decidable language will truth-table reduce to any language without making any oracle call. And any undecidable language cannot truth-table reduce, nor Turing reduce to a decidable one. So the problem really is just an exercise of thinking about the definition -this is not a criticism, that is an important kind of exercise.2012-05-15
  • 0
    @plm: That looks like an answer to me.2012-05-16

1 Answers 1

6

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.