computer-science - NP困難の非循環的定義は何ですか?

Question

ウィキペディアによると、概念NP、NP 完全、およびNP ハードを理解しようとしています。

与えられたテキストを正しく理解している場合:

編集：デビッドに従って修正

NP == 答えが多項式時間で検証できる決定問題 (解が与えられた場合)

NP完了== NPとNPハードを同時に

NP ハード==多項式時間チューリングで還元可能なNP 完全問題があります。

ですから、NP完全性の概念を理解するためには、まずNP硬度を理解する必要があります。そこで、上記のステートメントに従ってNP ハードとは何かを分析してみます。だから私は得る：

NP ハード== NP ハードである と同時にNPである問題があり、それに還元できます。しかし、定義には循環があります。非循環的定義とは何ですか?

Answer 1

また、任意の NP 問題を多項式時間で還元できるように、NP 完全を問題として定義することもできます。その定義により、サイクルが削除されます。

あなたの NP-hard の定義は逆のようです。ある NP 完全問題 (したがってすべての NP 問題) が多項式時間でその問題に還元できる場合、その問題は NP 困難であるはずです。

ここで詳細を確認できます: http://en.wikipedia.org/wiki/P_versus_NP_problem