何かがNPハードであることを証明するには、なぜNPコンプリートからそれを減らす必要があるのですか？

Question

ウィキペディアから：

問題Hは、h（すなわち、l≤th）に還元可能である多項式時間を還元可能であるNP完全な問題lがある場合にのみNPハードです。

なぜ問題（wと呼ばれる）が必要から削減されているのですか？なぜそれは単にNPハードであることができないのですか？ wがNPではなく「ハード」であることを気にするもののようです。

考え？

Answer 1

できる。実際、2番目の段落は最初の段落を意味します。

NPハードの問題Hが問題Xに対して多項式に還元可能であると仮定します。定義上、Hに対して多項式に還元可能なNP完全な問題Cが存在します。両方の減少は多項式であるため、多項式時間でCにXを減らすことができます。したがって、NP完全な問題Cは、多項式時間でXに還元できます。したがって、問題XはNPハードです。

Answer 2

あなたがあなたの問題のnp-hardnessを証明するのに十分な問題に対してNPハードの問題を多項式に減らすことができる場合。ただし、特定のNPハードの問題は、NPハード自体であるにもかかわらず、問題に対して多項式に還元できない場合があります。

さらに、削減によってnp-hardnessを証明する必要はありません。直接証明することもできます。