NP-completo

En teoría de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NP-completo son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad P. La razón es que de tenerse una solución polinómica para un problema de NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico.

Como ejemplo de un problema NP-completo está el problema de la suma de subconjuntos que se puede enunciar como sigue: dado un conjunto S de enteros, ¿existe un subconjunto no vacío de S cuyos elementos sumen cero? Es fácil verificar si una respuesta es correcta, pero no se conoce mejor solución que explorar todos los 2ⁿ-1 subconjuntos posibles hasta encontrar uno que cumpla con la condición.

Soluciones aproximadas

Actualmente, todos los algoritmos conocidos para problemas NP-completos utilizan tiempo exponencial con respecto al tamaño de la entrada. Se desconoce si hay mejores algoritmos, por la cual, para resolver un problema NP-completo de tamaño arbitrario se utiliza uno de los siguientes enfoques:

• Aproximación: Un algoritmo que rápidamente encuentra una solución no necesariamente óptima, pero dentro de un cierto rango de error. En algunos casos, encontrar una buena aproximación es suficiente para resolver el problema, pero no todos los problemas NP-completos tienen buenos algoritmos de aproximación.
• Probabilístico: Un algoritmo probabilístico obtiene en promedio una buena solución al problema planteado, para una distribución de los datos de entrada dada.
• Casos particulares: Cuando se reconocen casos particulares del problema para los cuales existen soluciones rápidas.
• Heurísticas: Un algoritmo que trabaja razonablemente bien en muchos casos. En general son rápidos, pero no existe medida de la calidad de la respuesta.
• Algoritmo genético: Algoritmos que mejoran las posibles soluciones hasta encontrar una que posiblemente esté cerca del óptimo. Tampoco existe forma de garantizar la calidad de la respuesta.

Definición de NP-completo

Un problema de decisión C es NP-completo si

1. es un problema NP y
2. todo problema de NP se puede transformar polinomialmente en él.

Una transformación polinomial de L en C es un algoritmo determinista que transforma instancias de l ∈ L en instancias de c ∈ C, tales que la respuesta a c es positiva si y solo si la respuesta a l lo es.

Como consecuencia de esta definición, de tenerse un algoritmo en P para C, se tendría una solución en P para todos los problemas de NP.

Esta definición fue propuesta por Stephen Cook en 1971. Al principio parecía sorprendente que existieran problemas NP-completos, pero Cook demostró (teorema de Cook) que el problema de satisfacibilidad booleana es NP-completo. Desde entonces se ha demostrado que miles de otros problemas pertenecen a esta clase, casi siempre por reducción a partir de otros problemas para los que ya se había demostrado su pertenencia a NP-completo; muchos de esos problemas aparecen en el libro de Garey and Johnson's de 1979 Computers and Intractability: A Guide to NP-completeness.

Un problema que satisface la segunda condición pero no la primera pertenece a la clase NP-hard.

Ejemplos

Un problema interesante en teoría de los grafos es el de isomorfismo de grafos: Dos grafos son isomorfos si se puede transformar uno en el otro simplemente renombrando los vértices. De los dos problemas siguientes:

Isomorfismo de grafos: ¿Es el grafo G₁ isomorfo al grafo G₂?

Isomorfismo de subgrafos: ¿Es el grafo G₁ isomorfo a un subgrafo del grafo G₂?

El problema de isomorfismo de subgrafos es NP-completo. Se sospecha que el problema de isomorfismo de grafos no está ni en P ni en NP-completo, aunque está en NP. Se trata de un problema difícil, pero no tanto como para estar en NP-completo.

La forma más sencilla de demostrar que un nuevo problema es NP-completo es primero demostrar que está en NP y luego transformar polinomialmente un problema de que ya esté en NP-completo a éste. Para ello resulta útil conocer algunos de los problemas que para los que existe prueba de pertenencia a NP-completo. Algunos de los más famosos son:

• Problema de satisfacibilidad booleana (SAT)
• Problema de la mochila (knapsack)
• Problema del ciclo hamiltoniano
• Problema del vendedor viajero
• Problema de la clique

Véase también:

• Categoría:Problemas NP-completos

Referencias

• Garey, M. and D. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, 1979. ISBN 0716710455 (Este es un libro clásico que desarrolla la teoría y clasifica muchos de los problemas NP-completos)
• S. A. Cook, The complexity of theorem proving procedures, Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York, 1971, 151-158
• Complejidad computacional de juegos y rompe-cabezas
• Tetris es difícil, aún para aproximarlo
• ¡Buscaminas es NP-completo!

Categorías

Encontrar

Encontrar