- ベストアンサー
計算理論についての質問です
NP完全の問題に関して指数時間アルゴリズムがあるからといってP≠NPとはいえないのはなぜでしょうか？
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (1)
- ranx
- ベストアンサー率24% (357/1463)
関連するQ&A
- ３彩色問題について質問です。
下記の問題が解けません。説明をよろしくお願いします。 P=NPとする。３彩色可能グラフがあるとして、有効な３彩色を作れる多項時間アルゴリズムが存在することを示せ。 ヒント：P=NPの仮定はグラフが多項時間内で３彩色可能なグラフかどうかを決定できることを示唆する。しかしP=NPの仮定にはこのテストがどのようになされるかしめされていない。大事なのはそのテストが探せるということを証明することである。
- 締切済み
- 数学・算数
- NP完全問題、NP困難問題についての質問です。
下記の問題が存在するとされているか、存在しないとされているか、もしくはどちらでもないかを教えてください。 どちらでもないものに対しては、簡単でいいのでなぜどちらでもないとされているのか教えて下さい。 1) 指数時間内で解けないNP完全問題 2) 指数時間内で解けないNP困難問題 3) NP内に存在するNP完全でない問題 よろしくお願いします。
- 締切済み
- 数学・算数
- Ｐ≠ＮＰ問題についての質問です。
Ｐ≠ＮＰ問題についての質問です。 この問題の議論されている意味が分かったような？分からんような？、なので質問します。 大方の研究者は、「Ｐ≠ＮＰ」ではないか？、という予想をしているようですが、この問題の結論は、 (1)Ｐ＝ＮＰ (2)Ｐ≠ＮＰ のどちらかひとつ、という解釈で間違いありませんか？ また、(1)と証明された場合、「全てのＮＰ問題はＰ問題に属する。」ことを示さねばなりませんよね？現在、ＮＰ問題（例：ナップザック問題、ハミルトン閉路問題・・・）とされている、全てのものが「ＮＰ⊂Ｐ」であることを証明しないと、「Ｐ＝ＮＰ」、であることは証明されたことになりませんよね？（全てについて調べなければいけないのか、それとも、ひとつでいいのか？） 一方で、(2)と証明された場合、「少なくともひとつのＮＰ問題はＰ問題に属さない。」ことを示せば大丈夫ですよね。 即ち、「何かひとつでいいから、ＮＰ問題であるけど、多項式アルゴリズムがない。」という問題を証明すればいいんですね？？（全てについて調べなければいけないのか、それとも、ひとつでいいのか？） 冒頭で書いた「Ｐ≠ＮＰが有力」というのは、「ひとつでいいからＰ問題に属さないＮＰ問題を見つければ良い。（多項式時間帰着可能でない、非決定性チューリングマシンが存在する。）」という裏付けであると考えていいのでしょうか。 ど素人なので勘違いしているかもしれませんが、解説お願いいたします。
- ベストアンサー
- 数学・算数
- 計算理論についての質問
計算理論についての質問です。 文脈自由文法gがεを受理するかどうかを判定するアルゴリズムが必ず存在するか、しないかを証明するという課題が出たのですが、 「アルゴリズムが存在する」ということはどうやったら証明できるのでしょうか？ 今、手元にはホップクロフトの「オートマトン言語理論計算論」があるのですが、「アルゴリズムが存在するかどうか」を証明するような問題が見つかりません。 学校でもこのような問題の例題はやっていないので、どなたか教えてください。 よろしくお願いしますm(__)m
- ベストアンサー
- 数学・算数
- NPクラス、Pクラス、NP完全問題について教えてください
こんにちは。 授業でNPやPというような言葉が出てくるのですがいまいち理解できません。 あまり理解できていない用語はPクラス、NPクラス、P問題、NP問題、NP完全問題、NP完全、NP困難、判定問題などです。似たような言葉がいろいろ出てきてよく分からないです。これらの用語のうちで意味が同じようなものもあるのでしょうか？ 自分なりに理解したことを書くと Pクラスというのはその問題が現実的な時間内で解けて、NPクラスとは時間がかかりすぎて解けないというふうに理解しています。 NPクラスには最長パスを求めるアルゴリズムや大きな素数同士の積の因数分解などだと思います。ウィキペディアでも調べたのですが言葉が難しくて曖昧にしか分かりませんでした。 また、判定問題やハミルトン問題などについても知りたいです。何か良いサイトがありましたら紹介してもらえるとありがたいです。 ご回答よろしくお願いします。
- ベストアンサー
- 数学・算数
- NP困難問題は必ず指数時間で解けますか？
宿題で大変困っています。もしよろしければ教えて下さい。 NP困難問題で指数時間で解けない問題は存在するのでしょうか? よろしくお願いします。
- ベストアンサー
- 数学・算数
- ボイルの法則での計算について
ボイルの法則を使った計算問題がわからないので教えてください。 0℃、1.0×10^5Paで２００ｍlの気体を、0℃、２５０ｍｌの体積にしたとき、圧力Ｐａは何lかという問題です。 ボイルの法則にあてはめて考えたらよいのはわかるのですが、解説を見ると、 1.0×10^5×0.20=P×0.25 P=8.0×10^4Pa ということでした。 スムーズな計算過程を教えて下さい。 １０の５乗にするために１０００００×０．２０をして０．２５で割ってしまって計算に時間を食っている私にアドバイスください。 またどうして、Ｐａの指数を10^4にしたり10^5にしたり変換しているのでしょうか？
- ベストアンサー
- 化学
- 情報理論：エントロピーの問題について。
【通報xが指数分布 p = (1/a)e^(-x/a) x≦0 = 0 x＞0 にしたがう。エントロピーを求めよ。 】 という問題があるのですが、この解きかたがわかりません。 普通に、 -∫[∞,0]plogp dx とおいて、解こうとしたのですが、値が∞になったりして、答えが出ません…。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- クリーク問題の計算複雑度
最近計算量理論を独習する中で「クリーク問題」なるものを知りました。 <クリーク問題> 入力: グラフG、正整数k 質問: Gは大きさkのクリーク(完全グラフ)を含むか? このクリーク問題の計算複雑度はNP完全とのことです。一方 <3クリーク問題> 入力: グラフG 質問: Gは大きさ3のクリークを含むか? この3クリーク問題の計算複雑度はPとのことです。そして3に限らず(5とか100とか)任意の数の場合でやはり計算複雑度はPとのことです。(下記URL参照) ここで疑問に思ったのですが、(PとNPは同一ではないという前提で)上の二つ(クリーク問題はNP完全、3クリーク問題はP)は矛盾してはいないでしょうか。すなわち、3クリーク問題、4クリーク問題、...がPで解けるのであればクリーク問題もPで解けるのでは、ということです。 どなたかこの件を解説していただけないでしょうか。 どうぞよろしくお願いいたします。 http://www.cs.bris.ac.uk/Teaching/Resources/COMS30126/30126probs2.pdf http://www.cs.bris.ac.uk/Teaching/Resources/COMS30126/ex_2_ans.pdf
- 締切済み
- 数学・算数
- 【P≠NP予想】容疑者Ｘの献身を観たのですが
容疑者Ｘの献身を観たのですが、 映画の一場面で「Ｐ≠ＮＰ問題」の話題が出てきました。 その中で、 「数学の問題について、自分で考えて答えを出すのと、他人から答えを聞いて、その答えが正しいかどうかを確認するのとではどちらが易しいか（難しいか）？ ただし、その問題には必ず答えが存在する。」 というセリフがありました。 恐らく、前者がクラスＰ、後者がクラスＮＰのことを表していると思われます。 しかし、「どちらが易しいか？（難しいか？）というのは、「Ｐ≠ＮＰ問題」の本質ではないような気がします。（Ｐの方がＮＰより解くのが大変ですよね・・） Ｐ≠ＮＰ問題の核心部分は、「Ｐ⊂ＮＰが成り立つかどうか？（ＮＰ⊂Ｐは自明）」ではないでしょうか？ 自分は映画を見ていて、「そんなの、他人から答えを聞いてその答えが正しいかどうかを確認する作業の方が、自分で答えを考え出すのより何百倍も簡単だろ！！」と思ってしまいました。 詳しい方解説お願いします！！！
- ベストアンサー
- 数学・算数
補足
図々しい話ですが もっと詳しく教えていただけると さらにありがたいんですが・・