Para provar que algo é NP-HARD, por que você precisa reduzir a partir de um NP-completo?

Question

Da Wikipedia:

Um problema H é np-hard se e somente se houver um problema de preenchimento de NP l que é o tempo polinomial reducível a H (ou seja, L ≤ Th).

Por que o problema (chama W) sendo reduzido da necessidade de ser NP-complete? Por que também não pode ser NP? Parece que você se importa em ser "difícil", não que esteja no NP.

Pensamentos?

Answer 1

Pode. De fato, seu segundo parágrafo implica o primeiro parágrafo.

Suponha que o Problema Hard H seja polinomialmente redutível ao Problema X. Por definição, existe um problema de preenchimento de NP que é polinomialmente redutível para H. Como ambas as reduções são polinomiais, você pode reduzir C a X no tempo polinomial. Portanto, o problema de NP-completo C é reduzível para X no tempo polinomial. Portanto, o problema x é np-duro.

Answer 2

Se você pode reduzir polinomialmente um problema de NP para o seu problema, o suficiente para provar a força do seu problema. No entanto, um problema específico de NP pode não ser polinomialmente redutível ao seu problema, mesmo que seja o próprio NP.

Além disso, você não precisa provar o NP-Hardness por redução, também pode provar isso diretamente.