Language \(L_1\) is polynomial time reducible to language \(L_2\) . Language…

GATE · 2015 · CS · Set 3 · Computer Science & IT

Language L1L_1 is polynomial time reducible to language L2L_2 . Language L3L_3 is polynomial time reducible to L2L_2, which in turn is polynomial time reducible to language L4L_4 . Which of the following is/are true?

I. if  L4∈PL_4 ∈ P , then L2∈PL_2 ∈ P

II. if L1∈PL_1 ∈ P or L3∈PL_3 ∈ P , then L2∈PL_2 ∈ P

III. L1∈PL_1 ∈ P , if and only if L3∈PL_3 ∈ P

IV. if L4∈PL_4 ∈ P , then L1∈PL_1 ∈ P and L3∈PL_3 ∈ P

  1. A.

    II only

  2. B.

    III only

  3. C.

    I and IV only

  4. D.

    I only

Attempted by 80 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…