PUERTA | PUERTA-CS-2005 | Pregunta 45

Considere tres problemas de decisión P1, P2 y P3. Se sabe que P1 es decidible y P2 es indecidible. ¿Cuál de las siguientes es VERDADERA?
(A) P3 es decidible si P1 es reducible a P3
(B) P3 es indecidible si P3 es reducible a P2
(C) P3 es indecidible si P2 es reducible a P3
(D) P3 es decidible si P3 es reducible al complemento de P2

Respuesta : (C)
Explicación:  
Antecedentes: En la teoría de la complejidad computacional, un problema de decisión tiene solo dos salidas posibles, sí o no.
Se dice que un problema de decisión es decidible si existe un método o algoritmo efectivo que devuelve una respuesta correcta de sí/no a ese problema.
Se dice que un problema de decisión es indecidible si no existe un solo algoritmo que siempre conduzca a una solución correcta de sí/no.

En términos de reducibilidad: A ≤ _p B denota que A es un problema de decisión que es reducible a B en tiempo polinomial p. Esto simplemente significa que la instancia de A se puede transformar en la instancia de B y siguiendo la solución de B podemos obtener una solución para el problema A.
Así que aquí podemos sacar algunas conclusiones:

1. If A ≤p B and B is decidable then A is also decidable.
This is because if there exists a specific algorithm for solving B and we can 
also reduce A to B then we can have a solution of A as well. Hence A is decidable.

However the reverse is not true i.e. if A ≤p B and A is decidable 
then B is also decidable because A can have an algorithm existing for its correct 
solution but might be the case that B does not.

2. If A ≤p B and A is undecidable then B is also undecidable.
This is because if A is undecidable even when it can be reduced to B that simply 
reflects even B cannot provide an algorithm by which we can solve B and hence A. 
So decision problem B is also undecidable.

Sin embargo, lo contrario tampoco es cierto aquí, es decir, si A ≤ _p B y B es indecidible, entonces A también es indecidible porque podría existir un algoritmo para A que pueda proporcionar una solución para A.

Usando las conclusiones mencionadas anteriormente, podemos decir que las opciones 1, 2 y 4 son falsas y la opción 3 es verdadera.

Option 1: P1 ≤p P3 and given P1 is decidable gives no conclusion for P3.
Option 2: P3 ≤p P2 and given P2 is undecidable gives no conclusion for P3.
Option 3: P2 ≤p P3 and given P2 is undecidable gives conclusion for P3 to be 
          undecidable.
Option 4: P3 ≤p P2’s complement and given P2 is undecidable therefore P2’s 
           complement is also undecidable gives no conclusion for P3.

Esta explicación es aportada por Yashika Arora.

Visite los siguientes artículos para obtener más información:
indecidibilidad y reducibilidad
Wikipedia: Reduction_(Complexity)

Quiz of this Question