The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+30 votes
2.7k 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.9k points)
edited by | 2.7k views
0
A Reducible to B  means every string of A is present in B. so something like this A is subset of B.

3 Answers

+35 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 (384k 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!
+13
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 .....
+1

    P1 ≤ P2 (P1 is reducible to P2)

If P1 is undecidable then P2 is Undecidable.

If P2 is Decidable then P1 is decidable.  

remember these as rules !

 

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

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

( P$_1$ ) is decidable =====> ( P$_1$ ) '  is also decidable.

( P$_2$ ) is undecidable =====> ( P$_2$ ) '  is also undecidable.

1. ( P$_2$ ) ' P$_3$ then P$_3$ is undecidable !

2. P$_3$ ( P$_1$ ) ' then P$_3$ is decidable !

0

 just a simple correction-  ( P2 ) is undecidable =====> ( P2 ) '  is also undecidable.

0
It's  a typo !

Thanks, i will update it.
0 votes

If there is any undecidable problem and if we are able to convert it into some other problem then that problem will also be undecidable.
If it is already know that a problem is decidable & if we convert some other problem to decidable problem then that problem will also be decidable.

So option C is right.

answered by Active (1.6k points)
edited by
–2 votes

answer is C

answered by (203 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
47,881 questions
52,231 answers
182,125 comments
67,651 users