GATE CS 2015 Set 3 Q.63 (CS Q.53): Asymptotic Analysis and Time/Space Complexity

Language $L_1$ is polynomial time reducible to language $L_2$ . Language $L_2$ is polynomial time reducible to $L_3$ , which in turn is polynomial time reducible to language $L_4$ . Which of the following is/are true?
I. if $L_1 \in P$ , then $L_2 \in P$
II. if $L_4 \in P$ or $L_3 \in P$ , then $L_2 \in P$
III. $L_1 \in P$ if and only if $L_3 \in P$
IV. if $L_4 \in P$ , then $L_2 \in P$ and $L_1 \in P$

II only

III only

II and IV only

I only

Official answer and solution

Official answer: C
From: Official GATE 2015 answer key

Solution

Apply transitivity and directionality of polynomial-time reductions.

We are given the chain of polynomial-time reductions:

L_1 \le_p L_2 \le_p L_3 \le_p L_4

By transitivity of polynomial-time reductions, $L_a \le_p L_b$ for all $1 \le a < b \le 4$ .

Fundamental property: If $A \le_p B$ and $B \in P$ , then $A \in P$ (polynomial tractability propagates backwards through reductions).

Evaluate statements:

Statement I: "if $L_1 \in P$ , then $L_2 \in P$ ". False: tractability does not propagate forward through reductions (a hard problem can reduce an easy problem).
Statement II: "if $L_4 \in P$ or $L_3 \in P$ , then $L_2 \in P$ ". If $L_3 \in P$ , then since $L_2 \le_p L_3$ , $L_2 \in P$ . If $L_4 \in P$ , then since $L_2 \le_p L_4$ , $L_2 \in P$ . In either case $L_2 \in P$ . True.
Statement III: " $L_1 \in P$ if and only if $L_3 \in P$ ". False: only the backward implication ( $L_3 \in P \implies L_1 \in P$ ) holds, not the forward implication.
Statement IV: "if $L_4 \in P$ , then $L_2 \in P$ and $L_1 \in P$ ". Since $L_1 \le_p L_4$ and $L_2 \le_p L_4$ , $L_4 \in P$ implies both $L_1 \in P$ and $L_2 \in P$ . True.

Therefore, statements II and IV only are true (Option C).

Final answer

Common trap

Assuming reductions are bidirectional equivalences rather than one-way upper bounds on relative problem hardness.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 3
Question: 63 of 65, printed as CS Q.53
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source