Um zu beweisen, dass etwas NP-Hard ist, warum müssen Sie sich von einer NP-Vervollständigung auf es reduzieren?
-
26-09-2019 - |
Frage
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?
Lösung
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.
Andere Tipps
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.