I am reading Automata Theory book by Hopcroft, Motwani and Ullman 2nd ed. In this book, there are these sentences:

In general, if we have an algorithm to convert instances of a problem $P_1$ to instances of a problem $P_2$ that have the same answer, then we say that $P_1$ * reduces to *$P_2$. We can use this proof to show that $P_2$ is at least as hard as $P_1$. Thus, if $P_1$ is not recursive, then $P_2$ cannot be recursive. If $P_2$ is non-RE, then $P_1$ cannot be RE.

I am quite confused due to last statement above because the book further states the following theorem:

If there is a reduction from $P_1$ to $P_2$, then:

  • If $P_1$ is undecidable then so is $P_2$.
  • If $P_1$ is non-RE, then so is $P_2$.

I dont know whether I should feel that the last statement above contradicts with the last statement in the first paragraph. So whats true?

If $P_2$ is non-RE, then $P_1$ cannot be RE.


If $P_1$ is non-RE, then so is $P_2$.

Or both mean the same and I am unnecessarily thinking that they are contradicting each other unnecessarily? Or the book is wrong?


You will reduce $P_1$ to $P_2$ if you know something "bad" about $P_1$, and you want to see if this extends to $P_2$.

It should read "If $P_1$ is non-RE, $P_2$ cannot be RE". If it is in the book, it's a typo.

  • $\begingroup$ thanks for confirmation, so its always source language (the one that we reduce) whose properties get translated to the destination language (the one to which we reduce)... $\endgroup$
    – anir
    Dec 24 '16 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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