Diferencia entre problema NP difícil y NP completo

Requisito previo: NP-Completitud 

Problema NP: 
El conjunto de problemas NP cuyas soluciones son difíciles de encontrar pero fáciles de verificar y se resuelven mediante una máquina no determinista en tiempo polinomial. 

Problema NP-Difícil : 
Un problema X es NP-Difícil si hay un problema NP-Completo Y, tal que Y es reducible a X en tiempo polinomial. Los problemas NP-Difíciles son tan difíciles como los problemas NP-Completos. El problema NP-Hard no necesita estar en la clase NP.

Problema NP-Completo : 

Un problema X es NP-Completo si existe un problema NP Y, tal que Y es reducible a X en tiempo polinomial. Los problemas NP-Completos son tan difíciles como los problemas NP. Un problema es NP-Completo si es parte tanto de NP como de NP-Hard Problem. Una máquina de Turing no determinista puede resolver el problema NP-Completo en tiempo polinomial. 

Diferencia entre NP-Hard y NP-Complete : 

NP-duro	NP-Completo
Los problemas NP-Difíciles (por ejemplo, X) se pueden resolver si y solo si hay un problema NP-Completo (por ejemplo, Y) que se puede reducir a X en tiempo polinomial.	Los problemas NP-Completos se pueden resolver mediante un algoritmo no determinista/máquina de Turing en tiempo polinomial.
Para resolver este problema, no tiene que estar en NP.	Para resolver este problema, deben ser problemas tanto NP como NP-difíciles.
No tiene por qué ser un problema de decisión.	Es exclusivamente un problema de Decisión.
Ejemplo: problema de detención, problema de cobertura de vértices, etc.	Ejemplo: determinar si un gráfico tiene un ciclo hamiltoniano, determinar si una fórmula booleana es satisfactoria o no, problema de satisfacibilidad de circuitos, etc.