- ベストアンサー
未解決問題 P＝NP について
revolution_2005の回答
- revolution_2005
- ベストアンサー率37% (55/146)
専門的なことなので、凄く簡単に説明すると、Pは現実的な時間で解ける問題、NPは現実的な時間で解けないと言われている問題のことです。 例えば、巡回セールスマン問題というものがあります。この問題は、N都市あって、ある都市から出発して、すべての都市を一度も重複せずに回って最初の都市に戻る最短の距離はどれかという問題です。 例をあげると、東京、大阪、北海道、沖縄の４都道府県をどう回れば最短距離になるかということです。 これは、全部の通り方を調べれば必ず答えを見つけることが出来ます。ですが、たった30都市になるだけで、現在ある最高のスーパーコンピュータでも、全通りを計算するのに何百兆年とかかってしまいます。 とても現実的な時間では解けないので、NP問題と言われています。 逆に、解の公式など、公式によって現実的な時間で解ける問題がP問題なのです。 それで、仮定されていることが、NP問題は実はP問題であるということです。つまり、現在NP問題と言われているものには、現実的な時間で解くための公式が存在し、P＝NPになるという仮定です。 このようなNP問題は現在巡回セールスマン問題以外にも、100近く存在し、もし一つでも解けたらノーベル賞ものです。世の中も、例えばこの巡回セールスマン問題がP問題と分かったら、最短経路が関係するあらゆるものが画期的になるでしょう。
関連するQ&A
- NPクラス、Pクラス、NP完全問題について教えてください
こんにちは。 授業でNPやPというような言葉が出てくるのですがいまいち理解できません。 あまり理解できていない用語はPクラス、NPクラス、P問題、NP問題、NP完全問題、NP完全、NP困難、判定問題などです。似たような言葉がいろいろ出てきてよく分からないです。これらの用語のうちで意味が同じようなものもあるのでしょうか？ 自分なりに理解したことを書くと Pクラスというのはその問題が現実的な時間内で解けて、NPクラスとは時間がかかりすぎて解けないというふうに理解しています。 NPクラスには最長パスを求めるアルゴリズムや大きな素数同士の積の因数分解などだと思います。ウィキペディアでも調べたのですが言葉が難しくて曖昧にしか分かりませんでした。 また、判定問題やハミルトン問題などについても知りたいです。何か良いサイトがありましたら紹介してもらえるとありがたいです。 ご回答よろしくお願いします。
- ベストアンサー
- 数学・算数
- Ｐ≠ＮＰ問題についての質問です。
Ｐ≠ＮＰ問題についての質問です。 この問題の議論されている意味が分かったような？分からんような？、なので質問します。 大方の研究者は、「Ｐ≠ＮＰ」ではないか？、という予想をしているようですが、この問題の結論は、 (1)Ｐ＝ＮＰ (2)Ｐ≠ＮＰ のどちらかひとつ、という解釈で間違いありませんか？ また、(1)と証明された場合、「全てのＮＰ問題はＰ問題に属する。」ことを示さねばなりませんよね？現在、ＮＰ問題（例：ナップザック問題、ハミルトン閉路問題・・・）とされている、全てのものが「ＮＰ⊂Ｐ」であることを証明しないと、「Ｐ＝ＮＰ」、であることは証明されたことになりませんよね？（全てについて調べなければいけないのか、それとも、ひとつでいいのか？） 一方で、(2)と証明された場合、「少なくともひとつのＮＰ問題はＰ問題に属さない。」ことを示せば大丈夫ですよね。 即ち、「何かひとつでいいから、ＮＰ問題であるけど、多項式アルゴリズムがない。」という問題を証明すればいいんですね？？（全てについて調べなければいけないのか、それとも、ひとつでいいのか？） 冒頭で書いた「Ｐ≠ＮＰが有力」というのは、「ひとつでいいからＰ問題に属さないＮＰ問題を見つければ良い。（多項式時間帰着可能でない、非決定性チューリングマシンが存在する。）」という裏付けであると考えていいのでしょうか。 ど素人なので勘違いしているかもしれませんが、解説お願いいたします。
- ベストアンサー
- 数学・算数
- 計算量(PやNP)について
ネット上で計算量理論に関する説明を読んでいますが、いまいち理解ができません。 例えば、木の形で表せれる問題で、一つのノードに対する子がN個(定数)あり、深さX(未知、変数)に答えがある場合、計算量は N^X(NのX乗) になると思います。 N^Xは計算量のクラス(NP困難やNP完全等)でいうと何に属するのでしょうか？
- ベストアンサー
- 数学・算数
- NP完全問題についての
NP完全問題についての質問です （1）NP完全問題とは多項オーダーの計算量で解決可能な問題のクラスですか、 問題のサイズをｎとしたとき「ｎの階乗」，「２のｎ乗」オーダーとなる問題は NP完全問題のうちには入らない？ （2）PSPACE完全問題とは何か（NP完全問題はPSPACE問題に含まれる（？）） 以上です．よろしくお願いします．
- ベストアンサー
- 数学・算数
- NP完全問題について。。
今、NP完全問題とSATについて勉強しています。 Wikiとかでも調べていて、一応自分なりに解釈をすすめて いるところですが、言い回しが難しくて理解しきれません。 簡単に、NP完全問題とSATについてのご説明を どなたかしていただけないでしょうか？ また良いサイトがあったら教えてください。
- 締切済み
- 数学・算数
- 【P≠NP予想】容疑者Ｘの献身を観たのですが
容疑者Ｘの献身を観たのですが、 映画の一場面で「Ｐ≠ＮＰ問題」の話題が出てきました。 その中で、 「数学の問題について、自分で考えて答えを出すのと、他人から答えを聞いて、その答えが正しいかどうかを確認するのとではどちらが易しいか（難しいか）？ ただし、その問題には必ず答えが存在する。」 というセリフがありました。 恐らく、前者がクラスＰ、後者がクラスＮＰのことを表していると思われます。 しかし、「どちらが易しいか？（難しいか？）というのは、「Ｐ≠ＮＰ問題」の本質ではないような気がします。（Ｐの方がＮＰより解くのが大変ですよね・・） Ｐ≠ＮＰ問題の核心部分は、「Ｐ⊂ＮＰが成り立つかどうか？（ＮＰ⊂Ｐは自明）」ではないでしょうか？ 自分は映画を見ていて、「そんなの、他人から答えを聞いてその答えが正しいかどうかを確認する作業の方が、自分で答えを考え出すのより何百倍も簡単だろ！！」と思ってしまいました。 詳しい方解説お願いします！！！
- ベストアンサー
- 数学・算数
- N=p^2+1 pは素数とすると・・・
ｐ＝２のときには N=5 ｐ＝３のときには N=10 ｐ＝５のときには N=26 ｐ＝７のときには N=50 この数字は何を意味しているでしょう。 ヒントは物理学とか科学です。
- 締切済み
- 科学
- ハミルトン閉路とNP
ハミルトン閉路問題はNPに属する、という事を証明したいのですが… これって HCがPに属することを証明すれば良いのでしょうか？ ちょっと迷走しちゃってます…
- 締切済み
- 数学・算数
- NPの電源を入ても立ち上がらない
VAIOのNP,PCG-GRT77E/Pですが 電源スイッチを入れ、初期画面が出る前、１から２秒の間に電源がダウンする。 解決方法を教えてください。
- ベストアンサー
- Windows XP
補足
なるほど。 P=NP問題が解決したら、素晴らしい未来が見えそうですね。 難しそうですが、解決される可能性はあるのでしょうか？