npハードに還元する

Question

Wikiによると、ポリタイムでのnpコンプリートの問題をAに変換すると、Aはnpハードです。 は

http://en.wikipedia.org/wiki/NP-hardを参照してください。しかし、以下のPDFファイルを使用すると、多項式時間で問題AにNP困難な問題を変換するとき、AがNPであることを言う - http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard.pdf

ハード1は、私は信じている必要がありますか？

Answer 1

両方。 NP-completeはNP-hardのサブセットです。 NP完全な問題は定義上、NP困難です。 1つのステートメントだけを覚えているなら、後者を覚えておいてください：NP-hardの問題を多項式時間で問題Aに減らすことができれば、AもNP困難です。

NP硬度は、NPの問題が多項式時間で問題に還元できる場合を指します。 NP完全性とは、問題がNPとNP困難の両方にある場合を指します。