Ejercicio 5 · Matemática Discreta UAB Juny 2022

a. Veracidad o falsedad: Si A es el problema de decisión de determinar si un grafo G es hamiltoniano, entonces B es NP-completo.

Solución: Falso / Falsa

a. Justificación: Si A es el problema de decisión de determinar si un grafo G es hamiltoniano, entonces B es NP-completo.

Solución: El problema del ciclo hamiltoniano es NP-completo, por lo que es NP-hard. Si $A \le_p B$ y $A$ es NP-hard, se deduce que $B$ es NP-hard, pero para ser NP-completo $B$ debe pertenecer además a la clase NP. Podría ocurrir que $B$ fuera indecidible (como el problema de la parada) o de complejidad superior a NP (como problemas EXPTIME), en cuyo caso sería NP-hard pero no NP-completo.

b. Veracidad o falsedad: Si A es NP-hard, entonces B es NP-completo.

Solución: Falso / Falsa

b. Justificación: Si A es NP-hard, entonces B es NP-completo.

Solución: Por la misma razón que en el apartado anterior: que $A$ sea NP-hard implica que $B$ es NP-hard, pero no garantiza que $B \in \text{NP}$.

c. Veracidad o falsedad: Si A ∈ NP, entonces es posible que B se pueda resolver en tiempo polinómico.

Solución: Verdadero / Verdadera

c. Justificación: Si A ∈ NP, entonces es posible que B se pueda resolver en tiempo polinómico.

Solución: Si $A$ es un problema en P (y todo problema en P está en NP), o si $A$ es trivialmente reducible a un problema tratable polinómicamente $B \in \text{P}$, entonces $B$ se puede resolver en tiempo polinómico. Por ejemplo, el problema de bipartición o conectividad en grafos está en NP y se reduce en tiempo polinómico a sí mismo (que está en P).

d. Veracidad o falsedad: Si B es verificable en tiempo polinómico, entonces A ∈ NP.

Solución: Verdadero / Verdadera

d. Justificación: Si B es verificable en tiempo polinómico, entonces A ∈ NP.

Solución: Que un problema de decisión sea verificable en tiempo polinómico por una máquina determinista con un certificado de tamaño polinómico es precisamente la definición formal de pertenecer a la clase NP, por lo que $B \in \text{NP}$. Dado que la clase NP es cerrada bajo reducciones polinómicas (si $B \in \text{NP}$ y $A \le_p B$, un certificado para la instancia reducida de $B$ sirve para verificar $A$ en tiempo polinómico), necesariamente se cumple que $A \in \text{NP}$.