engineering recuitment GATE CSE 2023-24 Test Series Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are true?
1
if L4 ∈ P, then L2 ∈ P
2
if L1 ∈ P or L3 ∈ P, then L2 ∈ P
3
L1 ∈ P, if and only if L3 ∈ P
4
if L4 ∈ P, then L1 ∈ P and L3 ∈ P