# GATE2015-3-53

3.4k views

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

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.

edited
0
0
I am not getting that line "But L1 is less harder than L1 as per condition 1" ???
0
Typo error  : But L1 is less harder than "L2" as per condition 1 . Because L2 is atleast as hard as L1 which means L2 can be more bigger problem than L1 or at least equal to L1.
0

although gatecse reference is good, my concept was clear through this https://www.iith.ac.in/~subruk/4510/aboutred.pdf

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.
0

In the above explanation all the  $<$  should be changed to $\leq$

If X is polynomial time reducible to Y, i.e  X $\leq$p  Y   then X is atmost as hard as Y. Therefore if X belongs to class P then, Y may or may not belong to class P.

0

you are right .....but here above sign (< ) is not mean to the less than i use this just for understanding purpose   .. consider this (L1<L2)  as  L1 is polynomial time reducible to language L2.

0

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.

It should be then L2 belongs to P may or may not be possible

0

@Anoop Sonkar Please explain part 4

Option C.

Reference as given by Adarsh Pandey :

## Related questions

1
6.1k views
Which of the following languages are context-free? $L_1: \left\{a^mb^na^nb^m \mid m, n \geq 1\right\}$ $L_2: \left\{a^mb^na^mb^n \mid m, n \geq 1\right\}$ $L_3: \left\{a^mb^n \mid m = 2n +1 \right\}$ $L_1$ and $L_2$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_3$ only
Let $L$ be the language represented by the regular expression $\Sigma^*0011\Sigma^*$ where $\Sigma = \{0, 1\}$. What is the minimum number of states in a DFA that recognizes $\bar{L}$ (complement of $L$)? $4$ $5$ $6$ $8$
Consider the following software items: Program-$X$, Control Flow Diagram of Program-$Y$ and Control Flow Diagram of Program-$Z$ as shown below The values of McCabe's Cyclomatic complexity of program-$X$, program-$Y$, and program-$Z$ respectively are 4, 4, 7 3, 4, 7 4, 4, 8 4, 3, 8