NPクラス、Pクラス、NP完全問題について教えてください

質問

こんにちは。
授業でNPやPというような言葉が出てくるのですがいまいち理解できません。
あまり理解できていない用語はPクラス、NPクラス、P問題、NP問題、NP完全問題、NP完全、NP困難、判定問題などです。似たような言葉がいろいろ出てきてよく分からないです。これらの用語のうちで意味が同じようなものもあるのでしょうか？

自分なりに理解したことを書くと
Pクラスというのはその問題が現実的な時間内で解けて、NPクラスとは時間がかかりすぎて解けないというふうに理解しています。
NPクラスには最長パスを求めるアルゴリズムや大きな素数同士の積の因数分解などだと思います。ウィキペディアでも調べたのですが言葉が難しくて曖昧にしか分かりませんでした。
また、判定問題やハミルトン問題などについても知りたいです。何か良いサイトがありましたら紹介してもらえるとありがたいです。
ご回答よろしくお願いします。

回答No.2

Tacosan · ベストアンサー

一番わかりにくい NP を中心に:
NP は Nondeterministic Polynomial の意味で, もともとは「非決定性チューリング機械によって多項式時間で判定できる」問題のクラスです. とはいわれても普通は「なんのこっちゃ」となるはずなので, もうちょっとわかりやすくいきましょう.
今は判定問題 (ある性質を持っているかどうかを答える問題) を考えているわけで, 普通は「与えられたもの」だけを使って答えることになります. これが「現実的な時間」=「多項式時間」でできるのが P.
これに対し, 「その性質を持っているときにはその証拠を示すことができる」という問題があります (もちろんその性質を持っていないときにはどんな「証拠」を持ってきてもダメ出しされる). このような問題のクラスを NP と呼びます.
例えばハミルトン閉路問題では, ハミルトン閉路を持つグラフに対しては「ああ, 確かに持っているね」と言わせるだけの証拠を示すことができます (具体的には「そのハミルトン閉路」そのものですが). 逆に, ハミルトン閉路を持たないグラフに対してはどんなものを持ってきても「ダメじゃん」と言われてしまいます. 従ってハミルトン閉路問題は NP に属します.
次に NP困難ですが, これは「NP に属するどの問題に対しても同等以上に難しい問題」のクラスです. でこの NP困難に属する問題のうち, NP にも属する問題を「NP完全問題」と呼びます. つまり NP困難問題は「NP に属する問題のうちで最も難しい問題」であるということになります.
で, クラスP は「『現実的な時間』=『多項式時間』で解ける問題」のクラスですがクラスNP は「時間がかかりすぎて解けない」ということではありません. P ⊂ NP なので, NP の中にも「簡単な問題」はあります.
あ～, 分からないところがあればどんどん指摘してください.

お礼

わかりやすい書き込みありがとうございました！
興味のある分野なので理解できたらいいなと思います。
お礼が遅れて申し訳ありません。いろいろ調べながら１時間ほど考えていました^^;

補足

丁寧な書き込みありがとうございます！
おかげさまで理解が深まってきました！恐縮ですが再度質問させてもらいます。

PとNPの違いについてはだいぶ分かりました。P ⊂ NP ということですね。ある問題の答えを示せばそれが正しいと判断できるのがPまたはNPで、証拠なしでかつ多項式時間でその答えを出すことができるものをクラスPというのですよね？ちなみに多項式時間とは本にはnが一つ増えると爆発的に増加すると本に書いてあったので2^nやn!といったものでいいんですよね？

NP困難やNP完全問題についてはいまいち理解できない部分があります。
NP困難とはNP問題を集めた中で難しいものを厳選（？）したような感じなんでしょうか？この難しいかどうかの判定はどのようにするのでしょうか？またNP完全問題＝NP困難問題なのでしょうか？
立て続けに質問してしまって恐縮です。

お暇であればご回答よろしくおねがいします

回答No.5

Tacosan

う～, 誤解されてる....
NP完全な問題が 1個でも多項式時間で解ければどの NP問題も多項式時間で解けて NP = P となります.
で, 「任意の NP困難な問題が 1個でも多項式時間で解ければどの NP問題も多項式時間で解ける」ことになります. つまり, NP困難問題は NP完全問題より簡単ではないということになります. 端的には「NP困難は NP完全より難しい」と言っても, まあそれほど間違っていません.

お礼

再度書き込みありがとうございます！！
ＮＰ＝Ｐということであればそれは重大なことなんですよね。
一般的にＮＰ＝Ｐではないことが予想されているから、そうでなければ難しい問題がなくなるというような内容を大学の教授が話していました。とりあいず

「任意の NP困難な問題が 1個でも多項式時間で解ければどの NP問題も多項式時間で解ける」
「NP困難は NP完全より難しい」

というのを理解しておきたいと思います。今までのご投稿のおかげでＮＰやＰに関しての概容は大体わかりました！あとは自力で本を読み直すなり勉強するなりして何とかなると思います！！それでもどうしても分からなくなった場合はまた質問させてもらいます。次はもっと発展した質問ができたらいいですけどね^^
今までサポートしてくださってありがとうございました！！

回答No.4

Tacosan

NP困難と NP完全は厳密には異なりますが, 分野によってはしばしば混同されます. 実際には, NP困難は「どの NP問題とも同等以上に難しい」問題のクラスなので, 「どの NP問題よりも明確に難しい」問題も含まれる (ボードゲームを考えるとよく出てくる PSPACE完全な問題は, おそらくどの NP問題よりも難しいと考えられていますが, このような問題も NP困難ということができます) ので NP困難≠NP完全なんですが. えっと... 話をややこしくするなら coNP とか出しますけど, どうします?
でこの「難しい」ですが, 「ある問題を, 他の問題に帰着して解けるかどうか」で判断します. つまり, 問題X を問題Y に帰着できる (問題X の問題例x を問題Y の問題例y に変換して, x の yes/no と y の yes/no を一致させることができる) ときに「問題X は問題Y より難しくない」(逆にいうと「問題Y は問題X と同等以上に難しい」) と判断します. P とか NP とかの文脈では「多項式時間帰着」, つまり「問題例を多項式時間で変換できる」とするのが普通ですが P の内部を考える (並列計算を考えたりするときに出てきます) ときにはもっと弱い帰着を使います.
あと, 「多項式」ってのは普通の多項式なので 2^n とか n! は入りません.

お礼

再度書き込みありがとうございます！
「難しい」という判断基準はおおよそ理解できました。他の問題と比較するのですね。
僕のイメージではＮＰ完全はＮＰ困難より難しく、ＮＰ完全が解ければ他のＮＰ問題も解ける（？）というふうに理解しました。しかし、実際ＮＰ完全を解くことは非常に難しい。
おかげ様で理解を深めることができました！！
参考になりました！！また、分からないことがあったらよろしくお願いします！！

回答No.3

rinkun

NP困難は必ずしもNPではないです。
これはPやNPが判定問題(yes/noで答えられる問題)のクラスだからです。
たとえばハミルトン閉路で言えば「グラフがハミルトン閉路を持つか」という問題はNPですが、「グラフのハミルトン閉路を求めなさい」だとNP困難だがNPではないわけです。
この辺はウィキペディアにも書いてありますけど。

お礼

回答ありがとうございます！！
ＰやＮＰについての定義を考えればたしかにＮＰ困難でもＮＰではないですね。参考になりました！！

回答No.1

a-saitoh

授業を受けておられるのなら、教科書をきっちり読むのがまずは近道だと思います。変な解説サイトを探すよりも。

決定性チューリングマシンで多項式時間で解ける問題がP,
非決定性チューリングマシンで多項式時間で解ける問題がNPです。

ウィキペディアの記述が難しすぎると言うのでしたら、もうすこし基礎を勉強されたほうがよろしいかと思います。十分平易にかかれています。

お礼

回答ありがとうございます。
教科書も読んだのですが自分には少々難しいようでした。最近は大学の教授ともそのことで相談していました。
自分でも努力しようとして図書館に行って本を３冊借りたところ大体のイメージはつかめたのですが、はっきりしたことがよく分からないので、さらに理解を深めたいと思い最終的にこのサイトで質問出せていただきました。専門家の方にとって平易にかかれているだろうと思いますが、学生にとっては初めての問題なので理解するのは難しいです。