ＮＰＣ概念の意義の問題点について

とにかく、何か分かっていることがあれば教えてください。

No.3 ベストアンサー 回答者： stomachman 回答日時： 2001/01/11 11:53

まあいいや、思いつくままに述べちゃおう。

申し訳ないけど推敲しませんので...
計算量の理論です。
NP問題とは、解を探索するには指数関数的時間が掛かるが、解を与えられたとき、それが解であることを検証するのは高々多項式時間でできる、っていうやつですね。
逆に言えば、解を探索するときにいっぱい場合分けが出来てしまう。X=TRUEかFALSEか。その分岐点に来たとき、コンピュータをもう一台持ってきて、メモリ・ディスク・レジスタの内容を全部コピーする。そして一方はX=TRUE, 他方はX=FALSEと仮定して計算を進める(non-deterministic)。こうするとコンピュータの数が指数関数的に増えていくけれども、どれかのコンピュータが「出来た！」と叫ぶまでの時間は多項式時間である。そういうことになります。
で、大概の難しい問題がこれに該当する。もっと難しい、本質的に指数関数時間掛かる奴や、決定不能の問題まであるけれど、諦めがつかない程度の難しさの奴がちょうどこのクラスである。さらにNP問題のいやらしい所は、これを多項式時間で解くことができない、という証明もどうしても出てこないという点である。ここまでの話では、もしあるNP問題が多項式時間で解ける、というアルゴリズムを示したら、それはその問題が実はP問題であった、というだけのことです。へたにやればNP、上手にやればP。
さて、NP問題の内に、その問題に他の問題が多項式時間の処理で帰着できるような、そういう問題のクラスがあることが分かった。それをNP完全問題という。これに関しては、「多項式時間で解くことができない」という証明も「実はP問題である」という証明も出来ていない。そのくせ「ＸＸという問題は実はNP完全でした」みたいな証明ならわさわさ出てくる。
もしひとつのNP完全問題について「実はP問題である」と証明したら、NP問題はみんなP問題になる（NP=P)。大発見！でもこんな事もはや誰も信じてないだろう。むしろ、「NP＝Ｐ？」は証明も、また反証も不可能であるような、いわゆる決定不能命題じゃないか、という疑いすらある。（ゲーデルの不完全性定理。「数学」カテゴリーの最近の質問にあるのでご参照ください。）
例えば、巡回セールスマン問題、ナップザック問題、いやさ素因数分解がそもそもNP完全だ。じゃあこれを逆に利用して、答えから問題を作る（これはP時間）ことによって通信の暗号につかっちゃおう、解くのには指数関数時間掛かるから安全だ。というのが公開鍵暗号です。
さて、多項式だ指数関数だ、ってこれはいずれも時間だけの話。時間のみならずメモリの使用量だって重要な計算リソースじゃないの？という尤もな反論がある。そこで両者を含めて計算量の理論が作られるようになった。
それから、幾ら多項式時間と言っても、その指数や係数が巨大で、とんでもなく時間が掛かるやつもある。こういうのは実用上はやっぱり使えない。こういうのアリ？という反論もある。逆に、実用上重要な行列のかけ算やFFTなどは、一所懸命、係数を僅かでも改良することをやっています。また計算幾何学、という分野がある。これなんかでも図形を対象にした処理の具体的なアルゴリズムを一所懸命研究している。計算誤差まで考慮すると手間が変わってきたりして、なかなかデリケートである。つまり具体的なアルゴリズムの研究＝泥臭い現場の研究と、この計算量の理論とが乖離して来ちゃった。計算量の理論がアルゴリズム研究の役に立ってない。ただの数学のお遊びに堕してるんじゃないの？

これが今までの話。

ここに来て、少し状況が変わりつつある。これまでの前提はノイマン型コンピュータ、あるいは万能オートマトン。一度にひとつの演算を順番にやっていく機械でした。ところが、DNAコンピュータというものは、非常に多くの生化学分子を演算素子として使うことによって、極端に並列度の高い計算ができる。数学者に言わせれば、所詮有限個の演算素子を並べただけの並列計算、NPがPかという問題には本質的に何の影響もない。でも実用上は違う。問題の規模が一定以下なら、NPでも指数関数時間の問題でも、多項式時間で解けてしまう筈。あるいは、ちょっと時代がさかのぼるけど光コンピュータ、これも並列度が高い上に、こいつは速い。NMR（核磁気共鳴）を使った原子核スピンによる計算も超並列計算だけど素子の数が莫大だ。その上を狙ってるのかおもちゃなのか、まだ分からない奴に「量子コンピュータ」がある。これはX=TRUEとFALSEの両方の状態を「混合状態」として「重ね合わせ」たまま計算を進めることが（今のところ僅かなステップだけだけど）出来るようである。リュードベリ原子（極度に励起された原子）１個に莫大な量の情報を載せる技術も出てきた。こうなると、公開鍵暗号なんて使い物にならなくなる？という状況にあります。

この回答への補足

stonachmanさん、すっごいです、この事の専門家なのですか？
私が調べなくてはならないのは、NP問題の中で、NPCということを定義することの意味、つまりNPCということを定義したために
そのことが数学界に（大袈裟ですが）もたらした効果と、しかし、始めに期待されたようには行かなかった、その現状と、
NPCから起こる悪影響、数学のこの方面の発展性を逆に別の方向に向けたり、止めたりしてしまっていること、
等がありましたら、教えてください。

ほんとにほんとに、先ほどの情報だけでもすごく助かっています。
感動してます！
もしよければ、さらに教えてください。
これから授業なので、その最中に先ほど送って頂いた内容を熟読してきます！

補足日時：2001/01/11 14:56

No.5 回答者： stomachman 回答日時： 2001/01/13 16:27

toronさんにお願いがあります。

この「OkWeb」もしくは「教えてgoo」は、質問者の悩みをよってたかって解決しよう、という主旨の他に、質問-回答を黙って読んでいる方も多いはずです。
そういう方々のために、「計算量が多項式時間である」「指数関数時間である」という事の簡単な説明を補足してから、この質問を閉じていただけないでしょうか。
宜しくお願いいたします。

この回答への補足

はい、計算量が多項式時間である、というのは、ある入力量ｎがあったときに、
それが正しい出力を得るまでにかかる時間が、n^2とかn^3といった、多項式で表せる範囲である、というもので、
指数関数時間である、というのは時間が2^nや3^ｎといった指数関数で表す分か借る、と言った意味です。
nが2や3である場合は両者にあまり変わりがないのですが、例えば1000だと考えると、指数関数のほうは表すことが不可能なくらい大きな物になってしまいます。
よって、難しい問題、一目では何がなんだか分からない問題を解こうとするとき、
それが多項式時間で解けるか、それとも指数関数時間かかってしまうのか判定できるということは、非常に重要なことなのです。

今回の私の質問は非常に専門的で、何がなんだか分からない人が多かったと思います。
ごめんなさい。でも、協力して頂けて非常に助かりました。

補足日時：2001/01/15 14:23

No.4 回答者： stomachman 回答日時： 2001/01/12 09:19

補足を拝見しました。

天下の一般人stomachmanの素人考えですが、ある概念が出来たからといって、それが数学界の足をひっぱったとは思いません。もっと別のオリジナルを考えるのが本物の数学者ですもん。そんな軟弱なものじゃないですよ。そりゃ、中にはNP=P問題を追求して一生を棒に振った奴もいっぱいいるでしょうが....

この回答へのお礼

stomachmanさん、どうもありがとうございました。
とても参考になりました。
参考書も借りてきたので、これから地道にレポートを書きます。

お礼日時：2001/01/12 16:21

No.2 回答者： stomachman 回答日時： 2001/01/11 10:57

なんと！　toronさんの補足以上に見事に要約するのは他の誰にも不可能なんじゃないか、と思うほどですが、具体的にあとどんな情報があ

れば、宜しいんでしょう？

No.1 回答者： stomachman 回答日時： 2001/01/09 22:08

これだけじゃ分かんないですよ。

NPCって何のことですか。
ひょっとしてNon-deterministic Polynomial Complete？

この回答への補足

はい、そうです。ＮＰ(Non-deterministic Polynomial）問題から多項式変換可能な
ＮＰ問題を、ＮＰの中のＮＰという意味で、ＮＰ完全(ＮＰ complete；ＮＰＣ）と定義した、
ＮＰＣのことです。このＮＰＣ問題を1つでの多く発見し、そのどれか1つについて
Polynomialかそうでないかを確定できれば良い、という問題設定のもとに過去30年ほど
様々な模索が試みられてきそうなのですが、それが成功していないとのことです。
ので、そのNPC概念の意義と問題点をまとめなくてはならないのですが・・・。

補足日時：2001/01/11 10:13