The Gateway to Computer Science Excellence

+37 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

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

+1

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

+21

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

+2

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?

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?

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?

+7

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

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

+2 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 known that a problem is decidable & if we convert some other problem to decidable problem then that problem will also be decidable.

**A <m (B) **means **A** cannot be harder than **B**.

So option C is right.

A Reducible to B means every string of A is present in B. so something like this A is a subset of B.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,394 answers

198,594 comments

105,445 users