こんにちは。
授業でNPやPというような言葉が出てくるのですがいまいち理解できません。
あまり理解できていない用語はPクラス、NPクラス、P問題、NP問題、NP完全問題、NP完全、NP困難、判定問題などです。似たような言葉がいろいろ出てきてよく分からないです。これらの用語のうちで意味が同じようなものもあるのでしょうか?
自分なりに理解したことを書くと
Pクラスというのはその問題が現実的な時間内で解けて、NPクラスとは時間がかかりすぎて解けないというふうに理解しています。
NPクラスには最長パスを求めるアルゴリズムや大きな素数同士の積の因数分解などだと思います。ウィキペディアでも調べたのですが言葉が難しくて曖昧にしか分かりませんでした。
また、判定問題やハミルトン問題などについても知りたいです。何か良いサイトがありましたら紹介してもらえるとありがたいです。
ご回答よろしくお願いします。
No.1
- 回答日時:
授業を受けておられるのなら、教科書をきっちり読むのがまずは近道だと思います。
変な解説サイトを探すよりも。決定性チューリングマシンで多項式時間で解ける問題がP,
非決定性チューリングマシンで多項式時間で解ける問題がNPです。
ウィキペディアの記述が難しすぎると言うのでしたら、もうすこし基礎を勉強されたほうがよろしいかと思います。十分平易にかかれています。
回答ありがとうございます。
教科書も読んだのですが自分には少々難しいようでした。最近は大学の教授ともそのことで相談していました。
自分でも努力しようとして図書館に行って本を3冊借りたところ大体のイメージはつかめたのですが、はっきりしたことがよく分からないので、さらに理解を深めたいと思い最終的にこのサイトで質問出せていただきました。専門家の方にとって平易にかかれているだろうと思いますが、学生にとっては初めての問題なので理解するのは難しいです。
No.2ベストアンサー
- 回答日時:
一番わかりにくい 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困難問題なのでしょうか?
立て続けに質問してしまって恐縮です。
お暇であればご回答よろしくおねがいします
わかりやすい書き込みありがとうございました!
興味のある分野なので理解できたらいいなと思います。
お礼が遅れて申し訳ありません。いろいろ調べながら1時間ほど考えていました^^;
No.3
- 回答日時:
NP困難は必ずしもNPではないです。
これはPやNPが判定問題(yes/noで答えられる問題)のクラスだからです。
たとえばハミルトン閉路で言えば「グラフがハミルトン閉路を持つか」という問題はNPですが、「グラフのハミルトン閉路を求めなさい」だとNP困難だがNPではないわけです。
この辺はウィキペディアにも書いてありますけど。
No.4
- 回答日時:
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! は入りません.
再度書き込みありがとうございます!
「難しい」という判断基準はおおよそ理解できました。他の問題と比較するのですね。
僕のイメージではNP完全はNP困難より難しく、NP完全が解ければ他のNP問題も解ける(?)というふうに理解しました。しかし、実際NP完全を解くことは非常に難しい。
おかげ様で理解を深めることができました!!
参考になりました!!また、分からないことがあったらよろしくお願いします!!
No.5
- 回答日時:
う~, 誤解されてる....
NP完全な問題が 1個でも多項式時間で解ければどの NP問題も多項式時間で解けて NP = P となります.
で, 「任意の NP困難な問題が 1個でも多項式時間で解ければどの NP問題も多項式時間で解ける」ことになります. つまり, NP困難問題は NP完全問題より簡単ではないということになります. 端的には「NP困難は NP完全より難しい」と言っても, まあそれほど間違っていません.
再度書き込みありがとうございます!!
NP=Pということであればそれは重大なことなんですよね。
一般的にNP=Pではないことが予想されているから、そうでなければ難しい問題がなくなるというような内容を大学の教授が話していました。とりあいず
「任意の NP困難な問題が 1個でも多項式時間で解ければどの NP問題も多項式時間で解ける」
「NP困難は NP完全より難しい」
というのを理解しておきたいと思います。今までのご投稿のおかげでNPやPに関しての概容は大体わかりました!あとは自力で本を読み直すなり勉強するなりして何とかなると思います!!それでもどうしても分からなくなった場合はまた質問させてもらいます。次はもっと発展した質問ができたらいいですけどね^^
今までサポートしてくださってありがとうございました!!
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 『完全<困難』 2 2022/11/28 06:36
- 数学 『4色問題③』 2 2022/11/14 00:31
- 計算機科学 判定問題がPに属するなら探索問題はNPに属する。では判定問題がNPに属するとき探索問題は? 2 2023/05/20 19:10
- 統計学 統計学 二項分布の正規近似について 2 2023/02/10 11:58
- 数学 『4色問題⓶』 3 2022/10/31 06:17
- 高校 勉強ができない。 4 2022/07/03 08:13
- 転職 転職の時、SPIテストの対策はどれくらい完璧にしましたか? 私は今アラサーなのですが、 ・英語系…中 2 2023/08/25 16:58
- 高校受験 数学の問題いくつか捨てても大丈夫?残り1ヶ月、点数が取れない教科ばっか勉強しても大丈夫? 高校受験 2 2023/01/07 17:55
- 大学受験 資格試験などの勉強で過去問題集の解説を理解する時、分からない用語を調べてどうするのが良いですか? 問 3 2023/06/18 17:18
- 一眼レフカメラ 一眼カメラのバッテリーについてSONY NP-FW50 PSE認証【海外パッケージ】 という物を見か 3 2023/02/13 23:44
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
タンジェントとアークタンジェ...
-
ゴンペルツ曲線の式
-
「グラフの概形を描け」と「グ...
-
数学の質問です。分数関数の分...
-
積分の面積を求める問題で 上−...
-
関数のグラフでy'''はなにを意...
-
数3 関数の極限 どういう問題の...
-
eのx乗のグラフはどうやって書...
-
f(x)=sin(1/x)(xは0以外)を0に...
-
関数の極限について
-
2点集中荷重片持ち梁について
-
数学です。このグラフの概形の...
-
10の1.2乗が、なぜ16になるのか...
-
「2次不等式2x²+3x+m+1<0を満た...
-
数学の問題を教えて下さい
-
4乗のグラフ
-
PHの方対数グラフ
-
微分方程式の「相図」ってなん...
-
指数関数と階乗。グラフで表し...
-
三角関数 y=cos3θのグラフの書...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
逆関数の合成関数について質問...
-
4乗のグラフ
-
関数のグラフでy'''はなにを意...
-
タンジェントとアークタンジェ...
-
数学の質問です。分数関数の分...
-
積分の面積を求める問題で 上−...
-
「グラフの概形を描け」と「グ...
-
Xについての方程式|x²-1|+x=Kが...
-
数3 関数の極限 どういう問題の...
-
指数関数と階乗。グラフで表し...
-
「2次不等式2x²+3x+m+1<0を満た...
-
関数の極限について
-
2点集中荷重片持ち梁について
-
10の1.2乗が、なぜ16になるのか...
-
ゴンペルツ曲線の式
-
Studyaid.D.Bは使いやすいですか?
-
数学
-
f(x)=sin(1/x)(xは0以外)を0に...
-
増減表について
-
対数グラフについて
おすすめ情報