No.3ベストアンサー
- 回答日時:
まあいいや、思いつくままに述べちゃおう。
申し訳ないけど推敲しませんので...計算量の理論です。
NP問題とは、解を探索するには指数関数的時間が掛かるが、解を与えられたとき、それが解であることを検証するのは高々多項式時間でできる、っていうやつですね。
逆に言えば、解を探索するときにいっぱい場合分けが出来てしまう。X=TRUEかFALSEか。その分岐点に来たとき、コンピュータをもう一台持ってきて、メモリ・ディスク・レジスタの内容を全部コピーする。そして一方はX=TRUE, 他方はX=FALSEと仮定して計算を進める(non-deterministic)。こうするとコンピュータの数が指数関数的に増えていくけれども、どれかのコンピュータが「出来た!」と叫ぶまでの時間は多項式時間である。そういうことになります。
で、大概の難しい問題がこれに該当する。もっと難しい、本質的に指数関数時間掛かる奴や、決定不能の問題まであるけれど、諦めがつかない程度の難しさの奴がちょうどこのクラスである。さらにNP問題のいやらしい所は、これを多項式時間で解くことができない、という証明もどうしても出てこないという点である。ここまでの話では、もしあるNP問題が多項式時間で解ける、というアルゴリズムを示したら、それはその問題が実はP問題であった、というだけのことです。へたにやればNP、上手にやればP。
さて、NP問題の内に、その問題に他の問題が多項式時間の処理で帰着できるような、そういう問題のクラスがあることが分かった。それをNP完全問題という。これに関しては、「多項式時間で解くことができない」という証明も「実はP問題である」という証明も出来ていない。そのくせ「XXという問題は実はNP完全でした」みたいな証明ならわさわさ出てくる。
もしひとつのNP完全問題について「実はP問題である」と証明したら、NP問題はみんなP問題になる(NP=P)。大発見!でもこんな事もはや誰も信じてないだろう。むしろ、「NP=P?」は証明も、また反証も不可能であるような、いわゆる決定不能命題じゃないか、という疑いすらある。(ゲーデルの不完全性定理。「数学」カテゴリーの最近の質問にあるのでご参照ください。)
例えば、巡回セールスマン問題、ナップザック問題、いやさ素因数分解がそもそもNP完全だ。じゃあこれを逆に利用して、答えから問題を作る(これはP時間)ことによって通信の暗号につかっちゃおう、解くのには指数関数時間掛かるから安全だ。というのが公開鍵暗号です。
さて、多項式だ指数関数だ、ってこれはいずれも時間だけの話。時間のみならずメモリの使用量だって重要な計算リソースじゃないの?という尤もな反論がある。そこで両者を含めて計算量の理論が作られるようになった。
それから、幾ら多項式時間と言っても、その指数や係数が巨大で、とんでもなく時間が掛かるやつもある。こういうのは実用上はやっぱり使えない。こういうのアリ?という反論もある。逆に、実用上重要な行列のかけ算やFFTなどは、一所懸命、係数を僅かでも改良することをやっています。また計算幾何学、という分野がある。これなんかでも図形を対象にした処理の具体的なアルゴリズムを一所懸命研究している。計算誤差まで考慮すると手間が変わってきたりして、なかなかデリケートである。つまり具体的なアルゴリズムの研究=泥臭い現場の研究と、この計算量の理論とが乖離して来ちゃった。計算量の理論がアルゴリズム研究の役に立ってない。ただの数学のお遊びに堕してるんじゃないの?
これが今までの話。
ここに来て、少し状況が変わりつつある。これまでの前提はノイマン型コンピュータ、あるいは万能オートマトン。一度にひとつの演算を順番にやっていく機械でした。ところが、DNAコンピュータというものは、非常に多くの生化学分子を演算素子として使うことによって、極端に並列度の高い計算ができる。数学者に言わせれば、所詮有限個の演算素子を並べただけの並列計算、NPがPかという問題には本質的に何の影響もない。でも実用上は違う。問題の規模が一定以下なら、NPでも指数関数時間の問題でも、多項式時間で解けてしまう筈。あるいは、ちょっと時代がさかのぼるけど光コンピュータ、これも並列度が高い上に、こいつは速い。NMR(核磁気共鳴)を使った原子核スピンによる計算も超並列計算だけど素子の数が莫大だ。その上を狙ってるのかおもちゃなのか、まだ分からない奴に「量子コンピュータ」がある。これはX=TRUEとFALSEの両方の状態を「混合状態」として「重ね合わせ」たまま計算を進めることが(今のところ僅かなステップだけだけど)出来るようである。リュードベリ原子(極度に励起された原子)1個に莫大な量の情報を載せる技術も出てきた。こうなると、公開鍵暗号なんて使い物にならなくなる?という状況にあります。
この回答への補足
stonachmanさん、すっごいです、この事の専門家なのですか?
私が調べなくてはならないのは、NP問題の中で、NPCということを定義することの意味、つまりNPCということを定義したために
そのことが数学界に(大袈裟ですが)もたらした効果と、しかし、始めに期待されたようには行かなかった、その現状と、
NPCから起こる悪影響、数学のこの方面の発展性を逆に別の方向に向けたり、止めたりしてしまっていること、
等がありましたら、教えてください。
ほんとにほんとに、先ほどの情報だけでもすごく助かっています。
感動してます!
もしよければ、さらに教えてください。
これから授業なので、その最中に先ほど送って頂いた内容を熟読してきます!
No.5
- 回答日時:
toronさんにお願いがあります。
この「OkWeb」もしくは「教えてgoo」は、質問者の悩みをよってたかって解決しよう、という主旨の他に、質問-回答を黙って読んでいる方も多いはずです。
そういう方々のために、「計算量が多項式時間である」「指数関数時間である」という事の簡単な説明を補足してから、この質問を閉じていただけないでしょうか。
宜しくお願いいたします。
この回答への補足
はい、計算量が多項式時間である、というのは、ある入力量nがあったときに、
それが正しい出力を得るまでにかかる時間が、n^2とかn^3といった、多項式で表せる範囲である、というもので、
指数関数時間である、というのは時間が2^nや3^nといった指数関数で表す分か借る、と言った意味です。
nが2や3である場合は両者にあまり変わりがないのですが、例えば1000だと考えると、指数関数のほうは表すことが不可能なくらい大きな物になってしまいます。
よって、難しい問題、一目では何がなんだか分からない問題を解こうとするとき、
それが多項式時間で解けるか、それとも指数関数時間かかってしまうのか判定できるということは、非常に重要なことなのです。
今回の私の質問は非常に専門的で、何がなんだか分からない人が多かったと思います。
ごめんなさい。でも、協力して頂けて非常に助かりました。
No.4
- 回答日時:
補足を拝見しました。
天下の一般人stomachmanの素人考えですが、ある概念が出来たからといって、それが数学界の足をひっぱったとは思いません。もっと別のオリジナルを考えるのが本物の数学者ですもん。そんな軟弱なものじゃないですよ。そりゃ、中にはNP=P問題を追求して一生を棒に振った奴もいっぱいいるでしょうが....
stomachmanさん、どうもありがとうございました。
とても参考になりました。
参考書も借りてきたので、これから地道にレポートを書きます。
No.1
- 回答日時:
これだけじゃ分かんないですよ。
NPCって何のことですか。ひょっとしてNon-deterministic Polynomial Complete?
この回答への補足
はい、そうです。NP(Non-deterministic Polynomial)問題から多項式変換可能な
NP問題を、NPの中のNPという意味で、NP完全(NP complete;NPC)と定義した、
NPCのことです。このNPC問題を1つでの多く発見し、そのどれか1つについて
Polynomialかそうでないかを確定できれば良い、という問題設定のもとに過去30年ほど
様々な模索が試みられてきそうなのですが、それが成功していないとのことです。
ので、そのNPC概念の意義と問題点をまとめなくてはならないのですが・・・。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 大学・短大 レポート課題について質問です。 課題が「講義を通して〇〇の概念について自分なりにまとめよ」というもの 3 2023/01/15 12:51
- 哲学 概念について 1 2023/04/09 15:09
- 数学 微分積分を理解できない人って脳の作りの問題でしょうか。情報系の大学に進み、微分積分が必須科目なんです 5 2022/07/14 08:40
- 哲学 概念と観念を中学生にでもわかる例えで理解してもらう 2 2022/05/12 08:01
- 大学受験 参考書の勉強法について質問なのですが、参考書を一通り終わらせて、二周目を行う際、問題だけ解けば良いで 2 2023/06/30 20:19
- その他(社会科学) 西暦上は明日が正月(1/1)ですが、西暦を採用してない国ってあるんですか?(つまり新年が違う国) 3 2022/12/31 18:59
- 人類学・考古学 いつからユダヤ教徒がユダヤ人になったのですか? 4 2022/05/06 15:51
- 芸術学 美術、芸術が得意な方に質問です。この問題の正解を教えてください。 設問1フォーヴィスムの特徴に当ては 3 2022/10/27 13:24
- 哲学 皆様、初めまして。 古代の中国哲学(宋学)に由来したようである「性情」の概念について知りたいです。 3 2023/07/08 14:14
- その他(メンタルヘルス) 近年ADHDとかアスペルガーなどと人を決めつけて差別する風潮がありますが、その一つ一つの症状自体は割 3 2023/03/26 01:58
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
計算方法について:人数の違うチ...
-
0.5時間などの時間計算の方法
-
1000分の3は何%ですか
-
結果が負の帯分数になる計算
-
付き合った日を1日から数える...
-
logeの計算
-
1000分の10の計算の仕方を教え...
-
医療費の計算方法を教えてくだ...
-
閏年の金利
-
複写機を購入した購入と同時に6...
-
1000円の3割の計算教えて下さい
-
126円の1.4倍はなんですか? 計...
-
10の0.3乗って??
-
ExcelでLog10を自然数に直すには
-
excelで板取計算。1枚の板から...
-
土嚢1体で何m3入りますか?
-
小1の息子ですが、 算数ノケイ...
-
何割引きか?暗算の方法教えて...
-
4を4つ使って1〜100を作って欲...
-
今日初コンビニバイトです。 私...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
量子コンピュータとか、量子コ...
-
計算方法について:人数の違うチ...
-
パソコンをつなげて高性能化?
-
チューリングマシンとオートマ...
-
mathematicaに関する質問 Sumに...
-
NPC概念の意義の問題点について
-
数学は将来どんな仕事で使いま...
-
教えてGooに関わる人工知能があ...
-
6-7高校数学
-
すばやく素因数分解する方法は?
-
理化学研究所のスーパーコンピ...
-
物理乱数と真性乱数の違いは何...
-
スパコンで20億年かかる、計算...
-
スパコンとパソコンはどう違う...
-
数学検定準2級の内容について
-
万能な記述形態って何種類ある...
-
0.5時間などの時間計算の方法
-
1000分の3は何%ですか
-
logeの計算
-
10の0.3乗って??
おすすめ情報