PUERTA | GATE-CS-2015 (Conjunto 3) | Pregunta 63

El lenguaje L1 es tiempo polinomial reducible al lenguaje L2. El lenguaje L3 es tiempo polinomial reducible a L2, que a su vez es tiempo polinomial reducible al lenguaje L4. ¿Cuál de los siguientes es/son verdaderos?

I. If L4 ∈ P, L2 ∈ P
II. If L1 ∈ P or L3 ∈ P, then L2 ∈ P
III. L1 ∈ P, if and only if L3 ∈ P
IV. If L4 ∈ P, then L1 ∈ P and L3 ∈ P 

(A) Solo II
(B) Solo III
(C) Solo I y IV
(D) Solo I

Respuesta: (C)
Explicación: Consulte https://www.geeksforgeeks.org/np-completeness-set-1/
Cuestionario de esta pregunta