Definición de NP-completo
Un
problema de decisión C es NP-completo si:
- C es un problema NP, y
- 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 l ∈ L en instancias de c ∈ C, 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.
