『完全＜困難』

PNP問題は御存知のことと思います。P問題は多項式時間で解ける問題、NP問題は非決定性多項式時間問題ですが、NP問題は大きく分けてNP完全とNP困難な問題となります。で、NP完全より困難の方が解くのが難しい、時間のかかる問題という認識なのですが、より具体的には、"完全"は解が与えられれば、それが正解かをP時間で確認可能、”困難”はNP時間かかる問題と思っているのですが、それでよろしいでしょうか？

No.2 回答者： Tacosan 回答日時： 2022/11/28 22:38

研究者って「既存の概念」に対しては案外保守的だからなぁ.... もちろん私がその辺の権限を持っているわけでもないんだけど.

さておき「解（と称するもの）が提供されても、正解か確認するのにNP時間、より具体的には、指数関数時間かかる問題とする」というのはちょっと問題があるような気がするねぇ. そもそも「NP時間」ってなんだよってところから突っ込まれるし「指数関数時間かかる」の「かかる」は「高々それだけあればできる」「少なくともそれだけは必要とする」のどちらの意味にもとれてしまう. でもって「指数関数時間というのは」のところでも「コンピュータでの」はきちんと定義しないとダメだし「ｎ∧ｎとかｎ∧ｎ！程度」は「『程度』の意味がはっきりとしない」し「∧」をべき乗と解するなら「n^n と (n^n)! と n^(n!) はどれも全く違う」ということになってしまう.

さらに駄目出しすると, その「定義」では「NP困難」の「NP」の意味がわからなくなるんだ. 今の定義なら「NP」と「NP困難」の関係は明確だけど, その「定義」では「NP」と「NP困難」がどのように関係する?

No.1 回答者： Tacosan 回答日時： 2022/11/28 10:21

ひらたくいうと

・NP困難: NP のどんな問題より難しい (簡単でない) 問題
・NP完全: NP のどんな問題より難しい (簡単でない) NP 問題
というイメージなので, NP完全などの問題も NP に属するんだけど NP困難な問題は NP に属するとは限らない (NP よりもっと難しいかもしれない).

本来「NP」は決定問題の集合なので「NP完全」というのは決定問題のみなんだけど, 決定問題でなくても「本質的に決定問題と同程度に難しい」問題もある. なので, 「NP完全」というときに決定問題以外のものを含むこともある.

この回答へのお礼

ありがとうございます。NP困難の中にはNPに含まれない問題もあるということですね。そこで改めてNP困難の定義として、ここに記した、「解（と称するもの）が提供されても、正解か確認するのにNP時間、より具体的には、指数関数時間かかる問題とする」のはどうでしょう？ここで、指数関数時間というのは、例えばTSP で、都市数＝nとしたときコンピュータでのステップ数にして、ｎ∧ｎとかｎ∧ｎ！程度かかるという意味です。この定義だと、NPに含まれる、まれないに関わらず、それなりに、”困難”の性質を表していると思うのですが…。

お礼日時：2022/11/28 21:27