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.