0

ウィキによると、ポリ時間の np complte 問題を A に変換すると、 A は np ハードです。http://en.wikipedia.org/wiki/NP-hardを参照

しかし、以下の pdf は、多項式時間で np ハード問題を問題 A に変換すると、A は np ハード http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard であると述べています。 pdf

どっちを信じればいい?

4

1 に答える 1

2

両方。NP 完全は NP 困難のサブセットです。NP 完全問題は、定義上、NP 困難です。1 つのステートメントだけを覚える場合は、後者を覚えておいてください。NP 困難な問題が多項式時間の問題 A に還元できる場合、A も NP 困難です。

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

于 2012-02-25T15:51:35.480 に答える