The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
2.2k views
  • 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.6k points)
edited by | 2.2k views

2 Answers

+34 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. 

http://gatecse.in/wiki/Some_Reduction_Inferences

answered by Veteran (359k points)
edited by
0
@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!
+9
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.
0
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?!
+1
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?
0
yes direct and contrapositive always equal
0
what is meaning of "P3 is at least as hard as P1" ?
Is it mean P3 is atleast decidable?
0
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?
+1
#srestha I think it means P3 can not be easier than P1 ... Some kind of lower bound .....
–2 votes

answer is C

answered by (191 points)
Answer:

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

40,995 questions
47,623 answers
146,903 comments
62,347 users