Para demostrar que algo es NP-Hard, ¿por qué necesitas reducirlo de un NP-Complete?

Question

De Wikipedia:

Un problema H es NP-HARD si y solo si hay un problema NP-completado L que es el tiempo polinomial reducible a H (es decir, l ≤ th).

¿Por qué el problema (llamarlo W) se reduce de la necesidad de ser NP-Complete? ¿Por qué no puede simplemente ser NP-Hard? Parece que lo que te importa es ser "difícil", no que esté en NP.

¿Pensamientos?

Answer 1

Puede. De hecho, su segundo párrafo implica el primer párrafo.

Suponga que el problema NP-Hard H es polinomialmente reducible al problema X. Por definición, existe un problema de NP-Completo C que es polinomialmente reducible a H. Dado que ambas reducciones son polinomiales, puede reducir C a X en tiempo polinómico. Por lo tanto, el problema de NP-Completo C es reducible a X en el tiempo polinomial. Por lo tanto, el problema X es NP-Hard.

Answer 2

Si puede reducir polinomialmente un problema difícil de NP a su problema que sea suficiente para demostrar la duración de NP de su problema. Sin embargo, un problema específico de NP-Hard puede no ser polinomialmente reducible a su problema a pesar de que es NP-Hard en sí mismo.

Además, no tiene que demostrar que NP-Hardness por reducción también puede probarlo directamente.