Per dimostrare che qualcosa è np-hard, perché è necessario ridurlo da un complesso NP?

Question

Da Wikipedia:

Un problema h è np-hard se e solo se esiste un problema di complesso NP che è il tempo polinomiale che si riduce a H (cioè, l ≤ th).

Perché il problema (lo chiama W) è ridotto dalla necessità di essere completato NP? Perché non può anche essere np-hard? Sembra ciò che ti interessa di essere "difficile" non che sia in NP.

Pensieri?

Answer 1

Può. In effetti, il tuo secondo paragrafo implica il primo paragrafo.

Supponiamo che il problema NP-hard H sia polinomiale riducibile al problema X. Per definizione, esiste un problema NP-completo C che è polinomiamente riducibile a H. Poiché entrambe le riduzioni sono polinomiali, è possibile ridurre da C a X nel tempo polinomiale. Pertanto, il problema C-NP-Complete è riducibile a X nel tempo polinomiale. Pertanto il problema X è np-hard.

Answer 2

Se riesci a ridurre polinomia un problema più duro del tuo problema che è sufficiente per dimostrare la deroga NP del tuo problema. Tuttavia, un problema specifico di NP-hard potrebbe non essere polinomiamente riducibile al tuo problema anche se è stesso NP-hard.

Inoltre, non è necessario dimostrare che la residenza NP per riduzione puoi anche dimostrarlo direttamente.