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 NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico. Si se demostrase que un problema NP-completo, llamémoslo A, no se pudiese resolver en tiempo polinómico, el resto de los problemas NP-completos tampoco se podrían resolver en tiempo polinómico. Esto se debe a que si uno de los problemas NP-completos distintos de A, digamos X, se pudiese resolver en tiempo polinómico, entonces A se podría resolver en tiempo polinómico, por definición de NP-completo. Ahora, pueden existir problemas en NP y que no sean NP-completos para los cuales exista solución polinómica, aun no existiendo solución para A.

Como ejemplo de un problema NP-completo encontramos 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 2n-1 subconjuntos posibles hasta encontrar uno que cumpla con la condición.


Definición de NP-completo

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

  1. C es un problema NP, y
  2. Todo problema de NP se puede transformar polinómicamente en C.

Se puede demostrar que C es NP demostrando que un candidato a solución de C puede ser verificado en tiempo polinómico.

Una transformación polinómica de L en C es un algoritmo determinista que transforma instancias de lL en instancias de cC, tales que la respuesta a c es positiva si y sólo 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 pertenece a la clase NP-hard independientemente de que satisfaga la primera.

Other Languages
català: NP-complet
čeština: NP-úplnost
dansk: NP-komplet
italiano: NP-completo
日本語: NP完全問題
한국어: NP-완전
Nederlands: NP-volledig
norsk nynorsk: NP-komplett
norsk bokmål: NP-komplett
português: NP-completo
srpskohrvatski / српскохрватски: NP-kompletni problemi
Simple English: NP-complete
slovenčina: NP-úplný problém
українська: NP-повна задача
Tiếng Việt: NP-đầy đủ
中文: NP完全