Considere dos idiomas L1 y L2, cada uno en el alfabeto ∑. Sea f : ∑ → ∑ una biyección polinomial computable en el tiempo tal que (∀ x) [x ∈ L1 si y si f(x) ∈ L2].
Además, sea f -1 también computable en tiempo polinomial.
¿Cuál de los siguientes NO PUEDE ser cierto?
(A) L1 ∈ P y L2 es finito
(B) L1 ∈ NP y L2 ∈ P
(C) L1 es indecidible y L2 es decidible
(D) L1 es recursivamente enumerable y L2 es recursivo
Respuesta: (C)
Explicación: Tenemos mapeo uno a uno para todas las instancias de L1 a L2.
L1 se da para ser indecidible. Además, L1 es un tiempo polinomial reducible a L2. (Por mapeo dado). Ahora, si L2 es decidible, entonces hay un algoritmo para resolver L2 en politiempo. Pero luego podemos resolver cada instancia de L1 en politiempo, haciendo que L1 también sea decidible. Prueba de contradicción
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA