recategorized by
9,027 views
38 votes
38 votes

Language $L_1$ is polynomial time reducible to language $L_2$. Language $L_3$ is polynomial time reducible to language $L_2$, which in turn polynomial time reducible to language $L_4$. Which of the following is/are true?

  1. $\text{ if } L_4 \in P, \text{ then } L_2 \in P$
  2. $\text{ if } L_1 \in P\text{ or } L_3 \in P, \text{ then } L_2 \in P$
  3. $L_1 \in P, \text{ if and only if } L_3 \in P$
  4. $\text{ if } L_4 \in P, \text{ then } L_3 \in P$
  1. II only
  2. III only
  3. I and IV only
  4. I only
recategorized by

4 Answers

Best answer
50 votes
50 votes
  1. $L_1$ is polynomial time reducible to $L_2$. So, $L_2$ is at least as hard as $L_1$. 
  2. $L_3$ is polynomial time reducible to $L_2$. So, $L_2$ is at least as hard as $L_3$. 
  3. $L_2$ is polynomial time reducible to $L_4$. So, $L_4$ is at least as hard as $L_2$. 

If $L_4$ is in $P, L_3$, $L_2$ and $L_1$ must also be in $P$. So, I and IV are true. 

We can have $L_1$ in $P$ and $L_2$ not in $P$, and none of the given conditions are violated. So, II is false. 

Assume $L_3$ not in $P$. Now, Since $L_2$ must be at least as hard as $L_3$, it must also be not in $P$. But $L_1$ is less harder than $L_1$ as per condition $1,$ and it can be in $P$ without violating any given conditions. So, III is false.

Hence, C is choice.

More Info: http://gatecse.in/wiki/Some_Reduction_Inferences

edited by
13 votes
13 votes
from question we can conclude that ...

L1<L2
L3<L2<L4
now take first statement
I. if L4 belongs P, then L2 belongs P this is true because L2 is polynomial time reducible to language L4
 

II. if L1 belongs P or L3 belongs P, then L2 belongs P not possible because L1, L3 is is polynomial time reducible to language L2, not L2 is polynomial time reducible to language L1,L2.
 

III. L1 belongs P, if and only if L3 belongs P this is not true because looking at L3 we can not define L1 or simply we can say that L1 is not polynomial time reducible to language L3
 

IV. if L4 belongs P, then L1 belongs P and L3 belongs P this is true because we know that L1<L2 & L3<L2 and L2 is polynomial time reducible to language L4 so we can say  L1&L2 also be polynomial time reducible to language L4.
So option C is correct.
3 votes
3 votes

Answer: Option C) I and IV only

Easy Solution:-

For Reducible to draw an arrow. Decidable moves backward, undecidable moves forward.

Given I) $\text{ if } L_4 \in P, \text{ then } L_2 \in P$  TRUE

  1. $\text{ if } L_1 \in P\text{ or } L_3 \in P, \text{ then } L_2 \in P$   FALSE
  1. $L_1 \in P, \text{ if and only if } L_3 \in P$  FALSE
  1. $\text{ if } L_4 \in P, \text{ then } L_3 \in P$   TRUE
Answer:

Related questions

44 votes
44 votes
2 answers
1
55 votes
55 votes
5 answers
2