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