- 締切済み
np完全問題とは何ですか
benderの回答
- bender
- ベストアンサー率45% (108/236)
Wikipedia 英語版の “NP-complete” （やその他）に以下のように書いてあります。 A decision problem C is NP-complete if 1. it is in NP and 2. it is NP-hard, i.e. every other problem in NP is reducible to it. ここで “decision problem” というのは、答えが Yes/No のいずれかで答えられるような種類の問題のことです。 また、始めの条件１に書いてあるNP と呼ばれる問題の集まりは、問題の答え（Yes/No）とその「求め方」がわかってしまえば、その答えが正しいかどうかのチェックは「素早く」できてしまう問題、そういった問題の集まり、とおおよそいえると思います。 さらに、条件２にある NP-hard と呼ばれる問題の集まりは、（すでに述べた）NPと呼ばれる問題のどの問題よりも、同じかそれ以上に難しいといえる問題の集まりことです。 この２つの条件を満たす NP-complete と呼ばれる問題になぜ関心が寄せられるのかというと、この条件からもわかるように、NP-complete 問題のうちどれか一つについて「素早く」解く方法が見つかると、すべてのNP 問題が「素早く」解けてしまうことになるからです。「興味深い問題」の多くは NP に含まれているので、それらすべてが「素早く」解けてしまう方法がみつかったらえらいことでしょうね。 ただ、NP-complete の問題はおそらく「素早く」は解けないのだろう、といわれているのですが、まだその証明がされていません。質問された方がその証明を発見した際には、あるいは、素早い解法を見つけた際には、その論文の謝辞に僕の名前も加えてもらえますか？
関連するQ&A
- Ｐ≠ＮＰ問題についての質問です。
Ｐ≠ＮＰ問題についての質問です。 この問題の議論されている意味が分かったような？分からんような？、なので質問します。 大方の研究者は、「Ｐ≠ＮＰ」ではないか？、という予想をしているようですが、この問題の結論は、 (1)Ｐ＝ＮＰ (2)Ｐ≠ＮＰ のどちらかひとつ、という解釈で間違いありませんか？ また、(1)と証明された場合、「全てのＮＰ問題はＰ問題に属する。」ことを示さねばなりませんよね？現在、ＮＰ問題（例：ナップザック問題、ハミルトン閉路問題・・・）とされている、全てのものが「ＮＰ⊂Ｐ」であることを証明しないと、「Ｐ＝ＮＰ」、であることは証明されたことになりませんよね？（全てについて調べなければいけないのか、それとも、ひとつでいいのか？） 一方で、(2)と証明された場合、「少なくともひとつのＮＰ問題はＰ問題に属さない。」ことを示せば大丈夫ですよね。 即ち、「何かひとつでいいから、ＮＰ問題であるけど、多項式アルゴリズムがない。」という問題を証明すればいいんですね？？（全てについて調べなければいけないのか、それとも、ひとつでいいのか？） 冒頭で書いた「Ｐ≠ＮＰが有力」というのは、「ひとつでいいからＰ問題に属さないＮＰ問題を見つければ良い。（多項式時間帰着可能でない、非決定性チューリングマシンが存在する。）」という裏付けであると考えていいのでしょうか。 ど素人なので勘違いしているかもしれませんが、解説お願いいたします。
- ベストアンサー
- 数学・算数
- NP完全問題について
NP完全問題について、最新の研究状況をお教えください。（当方、理系の大学出で、少し概念は学びました）また、今関連のHPやメーリングリストがありましたらお教えください。
- 締切済み
- 数学・算数
- NP完全問題について。。
今、NP完全問題とSATについて勉強しています。 Wikiとかでも調べていて、一応自分なりに解釈をすすめて いるところですが、言い回しが難しくて理解しきれません。 簡単に、NP完全問題とSATについてのご説明を どなたかしていただけないでしょうか？ また良いサイトがあったら教えてください。
- 締切済み
- 数学・算数
- NP完全問題についての
NP完全問題についての質問です （1）NP完全問題とは多項オーダーの計算量で解決可能な問題のクラスですか、 問題のサイズをｎとしたとき「ｎの階乗」，「２のｎ乗」オーダーとなる問題は NP完全問題のうちには入らない？ （2）PSPACE完全問題とは何か（NP完全問題はPSPACE問題に含まれる（？）） 以上です．よろしくお願いします．
- ベストアンサー
- 数学・算数
- あらゆる社会的問題は国民みんなの為にある。
私は一つの発見をしました。それはあらゆる社会的問題は国民みんなの為になる答えこそが正しいのだ、ということです。そもそも国民の為にならない答えなど答えではありません。 消費増税も国民の為に上げるべきだ、上げるべきでないと議論になっています。憲法改正も国民の為に改正すべき、改正すべきではないと議論されています。いじめ問題も、教育問題もすべて国民みんなの為になる答えこそ正しいのです。このようにあらゆる社会的問題は国民の為にあるのです。これは大きな発見です。 今まで死刑問題は人権に合わないから死刑は正しくないという人もいます。また人の命は命で償うべきだから死刑は賛成だ、などと議論されてきましたがそれは間違いです。そうではなくあらゆる社会的問題は国民みんなの為になる答えが正しいのです。どうすれば国民の為になるのか、犯罪が減るのかと議論すればいいのです。人権などに合致しないから死刑は間違っているというのは間違った議論です。 また日本では核問題については核廃絶が正しいとされています。しかしそれは間違いです。核を持つことが国民の為であるならば核を持つことが正しいのです。核を持つことが国民の為にならないならば核を持つのは間違いとなるのです。核廃絶が正しいと決めつけていないで、どちらが国民の為になるのかとみんなで議論すべきなのです。 このようにあらゆる社会的問題は国民の為という視点をもって議論すれば国民の為になる正しい答えに辿り着けると思うのです。 この考えに対して皆さんどう思いますか？教えてください。
- 締切済み
- 哲学・倫理・宗教学
- 人類のエネルギー問題
現在、人類の大きな課題の一つとしてエネルギー問題があり、様々な場所で議論されています、しかしエネルギー問題の本質の議論は必ずしも一致していません（例１：石油に代わるエネルギーを探すのが一番大切 例２：人類の人口増加がエネルギー問題の一番の問題なので抑制させる対策をとる事が大事←私はここだと思います）。 そこでここをお読みいただいているあなたはエネルギー問題の本質はどこにあると思いますか？幅広い意見をお待ちしております。
- 締切済み
- 自然環境・エネルギー
- NP完全問題、NP困難問題についての質問です。
下記の問題が存在するとされているか、存在しないとされているか、もしくはどちらでもないかを教えてください。 どちらでもないものに対しては、簡単でいいのでなぜどちらでもないとされているのか教えて下さい。 1) 指数時間内で解けないNP完全問題 2) 指数時間内で解けないNP困難問題 3) NP内に存在するNP完全でない問題 よろしくお願いします。
- 締切済み
- 数学・算数
- 温暖化問題は議論すら始められないのではないでしょうか？意見聞かせて下さい
朝まで生テレビを見て思ったのですが、議論を始めるのに必要なのは、確かな事実です。 議論＝理想までの過程の模索であり、そのためには現状認識が不可欠です。 よって事実が極度に曖昧な中での議論は無意味です。 にも関わらず、熱狂される温暖化の議論において ・温暖化しているのか否か(寒冷化か) ・もししているのなら原因は人間か ・温暖化は人間に悪影響を与えるか 議論の根幹になる基本的な事実の全てが、科学的に分かっていないようです。 もちろん私は武田さんみたいに、環境問題なんかないんだ！詐欺だ！と懐疑論ばかり主張したいわけではありません。 ただ、議論をするにはまだ早いのでは、と思っているのです どうして議論の根幹になる事実の全てがこんなにもはっきりしない中で議論が行われ、各国がCO2何%減らした減らさないの話まで進んでしまうのでしょうか。 もちろん多数派が主張する事実を仮定に議論が進められているわけですが、少数派の主張する事実も厳然としています。 仮定も曖昧過ぎます。 これでは議論は妄想や宗教です。 よって、この議論は、科学者の研究が進んで事実が少し程度分かってからで良いと私は思っています。 皆さんはどう考えていますか？
- 締切済み
- 自然環境・エネルギー
- 竹島問題でキレない韓国人は、いますか?
よく韓国人と竹島の領属問題を議論すると今まで温和な人が突然キレるという話をよく聞きますが竹島問題について冷静に議論できる韓国人は、いるのでしょうか? 経験のある方お教えください。
- 締切済み
- 国際問題