The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+23 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?

- $P_3$ is decidable if $P_1$
_{ }is reducible to $P_3$ - $P_3$ is undecidable if $P_3$ is reducible to $P_2$
- $P_3$ is undecidable if $P_2$ is reducible to $P_3$
- $P_3$ is decidable if $P_3$ is reducible to $P_2$'s complement

+31 votes

Best answer

- 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.
- 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.
- 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**. - Complement of an undecidable problem is undecidable. Now, reducing to an undecidable problem can't prove $P_3$ is decidable.

@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!

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?!

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?

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?

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,231 answers

114,271 comments

38,803 users