0
$\begingroup$

If P1<=P2 means P1 is reducible to p2,then which is true?

1 If P1 is RE But Not REC,P2 is also RE but not REC?

2.If P2 is RE But Not REC,P1 is also RE but not REC?

As per my knowledge,if P1 is undecidable then P2 is also undecidable,so if I consider this property,then as RE BUT NOT REC is also undecidable,then answer will be 1 is true.

Also I know if P2 is RE then P1 is also RE ,so as per this result,as RE BUT NOT REC is also RE,so 2 is true.

But AFAIK,both statements are not correct.Please help me with correct answer

Please clarify.

$\endgroup$
3
  • $\begingroup$ What exactly is your question? What do you want clarified? Are you asking us to check your work? $\endgroup$
    – D.W.
    Jan 13, 2017 at 6:20
  • $\begingroup$ Updated question $\endgroup$ Jan 13, 2017 at 7:08
  • $\begingroup$ $P_{1}\leq_{p} P_{2}$ means that $P_{1}$ is no more harder than $P_{2}$. So fi $P_{1}$ lies in $RE\setminus REC$ then same applies to $P_{2}$. But in number 2 this is not the case. The reduction does not rule out the existence of a decider for $P_{1}$. $\endgroup$
    – Sorrop
    Jan 13, 2017 at 8:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.