Language \(L_1\) is polynomial time reducible to language \(L_2\) . Language…
2015
Language \(L_1\) is polynomial time reducible to language \(L_2\) . Language \(L_3\) is polynomial time reducible to \(L_2\), which in turn is polynomial time reducible to language \(L_4\) . Which of the following is/are true?
I. if \(L_4 ∈ P \), then \(L_2 ∈ P \)
II. if \(L_1 ∈ P \) or \(L_3 ∈ P \) , then \(L_2 ∈ P \)
III. \(L_1 ∈ P \), if and only if \(L_3 ∈ P \)
IV. if \(L_4 ∈ P \) , then \(L_1 ∈ P \) and \(L_3 ∈ P \)
- A.
II only
- B.
III only
- C.
I and IV only
- D.
I only
Attempted by 57 students.
Show answer & explanation
Correct answer: C
Key facts about polynomial-time reductions: A reduction from language A to language B (A ≤p B) means that a polynomial-time decider for B yields a polynomial-time decider for A. Reductions are transitive.
If A ≤p B and B ∈ P, then A ∈ P: compute the reduction in polynomial time and then run B's polynomial-time decider.
If A ≤p B and B ≤p C then A ≤p C (transitivity).
Evaluate each statement:
Statement I: True. Since L2 reduces to L4 and L4 ∈ P, by the first fact L2 ∈ P.
Statement II: False. L1 ∈ P (or L3 ∈ P) does not give any algorithm for L2 because reductions are given from L1 and L3 to L2, not from L2 to them. The direction matters: a reduction A ≤p B lets you solve A if you can solve B, not the other way around.
Statement III: False. Both L1 and L3 reducing to L2 does not imply they reduce to each other. An if-and-only-if requires reductions in both directions between L1 and L3.
Statement IV: True. From L2 ≤p L4 and L4 ∈ P we get L2 ∈ P; then because L1 ≤p L2 and L3 ≤p L2, both L1 and L3 are in P.
Conclusion: Statements I and IV are true; II and III are false. The correct selection is I and IV only.
A video solution is available for this question — log in and enroll to watch it.