Reducibilidad del tiempo polinomial

Question

$ L_1 $ y $ L_2 $ son dos idiomas definidos en el alfabeto $ sum $. $ L_1 $ es reducible a $ L_2 $ en tiempo polinomial. ¿Cuál de los siguientes no puede ser verdad?

• $ L_1 en P $ y $ L_2 $ es finito
• $ L_1 en np $ y $ l_2 en P $
• $ L_1 $ es indecidible y $ L_2 $ es decidible
• $ L_1 $ es recursivamente enumerable y $ L_2 $ es recursivo

Mi razonamiento es el siguiente

Si $ a le_p b $ y $ b en P $, entonces $ A $ puede reducirse a $ B $ en tiempo polinomial y resolverse en tiempo polinomial que hace $ A en P $. Por lo tanto, inicialmente pensé en la segunda opción como falsa y, por lo tanto, la respuesta correcta.

Sin embargo, utilizando el mismo argumento sobre la reducción de mapeo, la tercera opción también parece ser falsa. La cuarta opción es la misma que la tercera.

No tuvo éxito en razonar cualquier cosa sobre la primera opción.

Para poner mis argumentos anteriores en contexto, estoy aprendiendo sobre la teoría de la computación y casi he escabrimido la superficie de la computabilidad y la teoría de la complejidad. Helo me afuera.

Answer 1

Tres de las opciones usan el mismo truco: si $ C1, C2 $ son dos clases de idiomas y $ C1 Subseteq C2 $; Entonces $ L1 en C2 $ no implica que $ L1 Notin C1 $.

La única opción que no se puede hacer es verdadera es 3: si hay una reducción del tiempo polinómico de un lenguaje indecidable $ L_1 $ a un lenguaje decidible $ L_2 $, entonces $ L_1 $ se vuelve decidible, solo construya una máquina de Turing que calcule la reducción y luego resuelva el problema usando el decisor por $ L_2 $) y esta es una contraddicción.