Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
@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 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

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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