The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+24 votes
  • Consider three decision problems $P_1$, $P_2$ and $P_3$. It is known that $P_1$ is decidable and $P_2$ is undecidable. Which one of the following is TRUE?
  1. $P_3$ is decidable if $P_1$ is reducible to $P_3$
  2. $P_3$ is undecidable if $P_3$ is reducible to $P_2$
  3. $P_3$ is undecidable if $P_2$ is reducible to $P_3$
  4. $P_3$ is decidable if $P_3$ is reducible to $P_2$'s complement
asked in Theory of Computation by Veteran (59.4k points)
edited by | 1.9k views

2 Answers

+33 votes
Best answer
  1. If $P_1$ is reducible to $P_3$, then $P_3$ is at least as hard as $P_1$. So, no guarantee if $P_3$ is decidable.
  2. If $P_3$ is reducible to $P_2$, then $P_3$ cannot be harder than $P_2$. But $P_2$ being undecidable, this can't say $P_3$ is undecidable.
  3. If $P_2$ is reducible to $P_3$, then $P_3$ is at least as hard as $P_2$. Since, $P_2$ is undecidable, this means $P_3$ is also undecidable -hence the answer.
  4. Complement of an undecidable problem is undecidable. Now, reducing to an undecidable problem can't prove $P_3$ is decidable.

answered by Veteran (342k points)
edited by
@arjun suresh sir...why is option b incorrect?
 we always use halting problem(which is undecidable ) or any other such undecidable problem, reduce other problems to the halting problem and by that we prove the other problem is also undecidable..
Can you clarify this please!
No, we never reduce any problem to halting problem and say that that problem is undecidable. Rather we reduce halting problem to a given problem and say that the problem is undecidable.
sir if the option says,

1. "P3 is undecidable, if P2's complement is reduced to P3," &

2. "P3 is decidable, if P3 is reduced to P1's complement"


 will it be correct?!
P1 ≤ P2 (P1 is reducible to P2)

If P1 is undecidable then P2 is Undecidable.

Contrapositive of above is

If P2 is Decidable then P1 is decidable.

Can we say like that arjun sir?
yes direct and contrapositive always equal
what is meaning of "P3 is at least as hard as P1" ?
Is it mean P3 is atleast decidable?
is it in syllabus?

and as per my knowledge P and NP hard problem is get eliminated from the syllabus from 2016 onwards.

and to understand this question, i think we have some knowledge about p and np hard problems.

correct me if i am wrong?
#srestha I think it means P3 can not be easier than P1 ... Some kind of lower bound .....
–2 votes

answer is C

answered by (189 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,526 questions
42,803 answers
42,166 users