Reducciones polinómicas y clases NP: ejercicios de verdadero o falso resueltos

Otras lenguas extranjeras3,03 KB

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.

Descargar

PDF Word HTML