Follow Us :

Dynamic Programming 16

0. 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?
I. If L4 ∈ P, L2 ∈ P
II. If L1 ∈ P or L3 ∈ P, then L2 ∈ P
III.L1 ∈ P or if and only if L3 ∈ P
IV. If L4 ∈ P then L1 ∈ P, then L3 ∈ P

  • Option : C
  • Explanation :
         L2 ≤ pL4
         L1 ≤ pL2
    If    L4 ∈ P
    then  L2 ∈ P
         L1 ∈ P,
Cancel reply
Cancel reply