ウィキペディアから：
問題Hは、多項式時間チューリングでHに還元可能な（つまり、L≤TH）NP完全問題Lがある場合にのみ、NP困難です。
なぜ問題（それをWと呼ぶ）がNP完全である必要から減らされるのですか？なぜそれはNP困難でもないのですか？NPではなく、Wが「ハード」であることを気にかけているようです。
考え？
4550 次
2 に答える
3
できる。実際、2番目の段落は最初の段落を意味します。
NP困難問題Hが問題Xに多項式還元可能であると仮定します。定義により、Hに多項式還元可能なNP完全問題Cが存在します。両方の還元は多項式であるため、多項式時間でCをXに還元できます。したがって、NP完全問題Cは、多項式時間でXに還元できます。したがって、問題XはNP困難です。
于 2010-08-06T19:10:26.437 に答える
0
NP 困難な問題を多項式で問題に還元できる場合、それは問題の NP 困難性を証明するのに十分です。ただし、特定の NP 困難な問題は、それ自体が NP 困難であっても、多項式で問題に還元できない場合があります。
さらに、還元によって NP 硬さを証明する必要はなく、直接証明することもできます。
于 2010-08-06T19:20:37.530 に答える