Ejercicios sobre reducciones polinómicas y clases de complejidad (español)
a) Si A es un problema de decidir si un grafo G dado es hamiltoniano, entonces B es NP-completo. FALSO
De A≤p B solo se deduce que B es NP-hard (al menos tan difícil como un problema NP-completo). Para ser NP-completo, además, tendría que cumplirse B ∈ NP, y eso no se garantiza: B podría estar fuera de NP (por ejemplo, ser PSPACE-completo).
b) Si A es NP-hard, entonces B es NP-completo. FALSO
Análogo al caso anterior: B es NP-hard, pero puede no pertenecer a NP. La condición de completitud requiere ambas cosas: B ∈ NP y B es NP-hard.
c) Si A es NP, entonces es posible que B se pueda resolver en tiempo polinómico. CIERTO
No hay contradicción: que A≤p B no...