¿Recuerda qué es un problema NP-completo? ¿En qué se diferencia de simplemente NP?

NP (tiempo polinómico no determinista) es una clase de problemas para los cuales la solución puede verificarse en tiempo polinómico. Es decir, si tienes un candidato a respuesta, puedes verificar rápidamente si es correcto o no.

Los problemas NP-completos son un subconjunto de NP que son a la vez los más "difíciles" en esta clase. Si alguien encontrara un algoritmo polinómico para resolver cualquier problema NP-completo, entonces todos los problemas en NP podrían resolverse en tiempo polinómico.

La principal diferencia:

• NP: problemas cuyas soluciones pueden verificarse rápidamente.
• NP-completo: problemas en NP a los que se puede reducir cualquier otro problema NP (es decir, son los "más difíciles" en NP).

Ejemplo: el problema del clique de tamaño máximo en un grafo es NP-completo, y el problema de verificar si un subconjunto de elementos suma a un número dado está en NP.