Reducciones polinómicas y clases NP: ejercicios de verdadero o falso resueltos
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 impone un límite inferior sobre la complejidad de B. Por ejemplo, si A está en P (recordemos que P ⊆ NP), podemos tomar B = A; entonces B se resuelve en tiempo polinómico.
d) Si B es verificable en tiempo polinómico, entonces A es NP. CIERTO
Si B es verificable en tiempo polinómico, entonces B ∈ NP. Dado que A≤p B y B ∈ NP, entonces A también está en NP, porque NP es cerrado bajo reducciones polinómicas.
Versión en catalán (Exercicis en català)
a) Si A és el problema de decidir si un graf G donat és hamiltonià, llavors B podria ser el problema SAT. CERT
El problema de decidir si un graf és hamiltonià (Cicle Hamiltonià) és NP-complet. El problema SAT (Satisfactibilitat booleana) també és NP-complet. Com que tots dos són NP-complets, existeixen reduccions polinòmiques en ambdues direccions: HAM ≤p SAT (es pot reduir el problema Hamiltonià a SAT) i SAT ≤p HAM (i viceversa).
b) Si A és NP-hard, llavors B és NP-complet. FALS
De A ≤p B només se’n dedueix que B és NP-hard. Per ser NP-complet caldria a més B ∈ NP, cosa que no està garantida: B podria viure fora de NP (per exemple, ser PSPACE-complet).
c) Si A és NP, llavors és possible que B es pugui resoldre en temps polinòmic. CERT
No hi ha cap restricció que impedeixi que B sigui “fàcil”. Per exemple: si A = 2-SAT (que està a NP) i triem B = 2-SAT, llavors B ∈ P. La reducció A ≤p B no dóna cap límit inferior sobre la complexitat de B.
d) Si B es pot reduir (en temps polinòmic) a un altre problema C, on C té complexitat temporal O(n10), llavors A és P. CERT
Tenim la cadena A ≤p B ≤p C. Compondre dues transformacions polinòmiques dóna una transformació polinòmica A ≤p C. Com que C es resol en temps polinòmic, podem resoldre A en temps polinòmic (el cost és un polinomi de polinomis, i per tant encara és un polinomi). Si C estigués en una classe més gran (per exemple, EXP), la conclusió no seria certa.