GATE CS 2015 Set 3 Q53 — Undecidability

To analyze the statements, we use the fundamental property of polynomial-time reductions ($\le_P$):

If $A \le_P B$ and $B \in P$, then $A \in P$.

We are given the following reductions:

1. $L_1 \le_P L_2$
2. $L_3 \le_P L_2$
3. $L_2 \le_P L_4$

Let's evaluate each statement:

• Statement I: If $L_4 \in P$, then $L_2 \in P$.
  Since $L_2 \le_P L_4$ and $L_4 \in P$, it directly follows that $L_2 \in P$. Thus, Statement I is TRUE.
• Statement II: If $L_1 \in P$ or $L_3 \in P$, then $L_2 \in P$.
  Reductions go from $L_1$ and $L_3$ to $L_2$. Knowing that the reduced-from (easier) language is in $P$ does not guarantee that the target (harder) language $L_2$ is in $P$. For example, $L_1$ could be a trivial language in $P$ while $L_2$ is NP-complete. Thus, Statement II is FALSE.
• Statement III: $L_1 \in P$ if and only if $L_3 \in P$.
  There is no direct reduction or dependency between $L_1$ and $L_3$. One could be in $P$ while the other is not. Thus, Statement III is FALSE.
• Statement IV: If $L_4 \in P$, then $L_3 \in P$.
  Polynomial-time reduction is transitive. Since $L_3 \le_P L_2$ and $L_2 \le_P L_4$, we have $L_3 \le_P L_4$.
  Since $L_3 \le_P L_4$ and $L_4 \in P$, it follows that $L_3 \in P$. Thus, Statement IV is TRUE.

Hence, only statements I and IV are true, which corresponds to option C.