Um zu beweisen, dass etwas NP-Hard ist, warum müssen Sie sich von einer NP-Vervollständigung auf es reduzieren?

Question

Aus Wikipedia:

Ein Problem H ist np-hard, wenn und nur wenn ein NP-Complete-Problem L vorhanden ist, das polynomiale Zeit ist, die auf H reduzierbar ist (dh L ≤ TH).

Warum muss das Problem (nennen Sie es W) von NP-Complete reduziert? Warum kann es nicht auch NP-Hard sein? Es scheint, als ob es Ihnen wichtig ist, "hart" zu sein, nicht dass es in NP ist.

Gedanken?

Answer 1

Es kann. Tatsächlich impliziert Ihr zweiter Absatz den ersten Absatz.

Angenommen, das NP-HART-Problem H ist polynomisch auf Problem X reduzierbar. Per Definition gibt es ein NP-Complete-Problem C, das polynomial auf H reduzierbar ist. Da beide Reduktionen polynomisch sind, können Sie C in der Polynomzeit C auf X reduzieren. Daher ist das NP-Complete-Problem C in der Polynomzeit auf x reduzierbar. Daher ist das Problem X NP-Hard.

Answer 2

Wenn Sie ein polynomial ein NP-harter Problem auf Ihr Problem reduzieren können, ist dies ausreichend, um die NP-Härte Ihres Problems zu beweisen. Ein spezifisches NP-HART-Problem ist jedoch möglicherweise nicht polynomial auf Ihr Problem reduzierbar, obwohl es sich selbst NP-HART selbst handelt.

Darüber hinaus müssen Sie nicht durch Reduktion nachweisen, dass Sie es auch direkt beweisen können.