【話題/学術】ついに解けた？賞金100万ドルがかけられた数学の難問『P≠NP予想』--インド人研究者が論文発表 [08/14]
1 名前：ライトスタッフ◎φ ★ 投稿日：2010/08/14(土) 13:18:14 ID:???
数学の難問「Ｐ≠ＮＰ予想」がついに解けた――。
そんな論文をインド人研究者が今月発表し、世界中の数学者の間で
話題になっている。
数学者らは早速、証明が正しいかどうかの検証作業に入った。
Ｐ≠ＮＰ予想は[http://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%AC%E3%83%8B%E3%82%A2%E3%83%A0%E6%87%B8%E8%B3%9E%E5%95%8F%E9%A1%8C:title=100万ドルの賞金がかけられた７大難問]の１つで、
仮に証明が正しければ歴史的な成果となる。
◎ソース
http://www.nikkei.com/news/headline/article/g=96958A9C93819595E3E1E2E2948DE3E1E2EAE0E2E3E2E2E2E2E2E2E2
2 名前：名刺は切らしておりまして[sage] 投稿日：2010/08/14(土) 13:20:20 ID:HadLDPt/
先越されたぁ
3 名前：名刺は切らしておりまして[sage] 投稿日：2010/08/14(土) 13:20:55 ID:SdEhFHzH
大学でずっとこの証明やってて
あと2割くらいで出来そうな目処がついてたのに・・・・・
あと1年くらいで俺も解けたのに･･･････････････・・・・・・・・・・・・・・・・・
▼ 4 名前：名刺は切らしておりまして[sage] 投稿日：2010/08/14(土) 13:22:23 ID:wr2sIaFa
>>3
ということで、次の課題はインド人の論文が間違ってることの証明だ。がんばれ。
11 名前：名刺は切らしておりまして[sage] 投稿日：2010/08/14(土) 13:33:07 ID:SdEhFHzH
>>4
この論文は間違ってないよ
悔しいけど
▼ 82 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 16:20:44 id:cOic2lUx
>>11
各所から「ここ間違ってる」ってツッコミが入ってるらしいで。
で、今急いで修正中。
10 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 13:32:27 ID:ibkx386I
Ｎが1以外ならＰ≠ＮＰが成り立つ。
こんなことは小学校の算数レベルじゃん。
11 名前：名刺は切らしておりまして[sage] 投稿日：2010/08/14(土) 13:33:07 ID:SdEhFHzH
NP完全なんてありえないのは常識的に分かるんだけど、
それを論理的に証明するのがね・・
3年で8割行ったからあと1年で完成するのを目指してたのに
単位もとらずに3年間これだけだった
中退するか・・
▼ 23 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 14:18:24 ID:/TPB602j
>>11
何してんだお前、自分で８割できたとか言ってても、英語で有名処に論文
を先に出さないと意味ないし出来てないのと同じだろ
中退じゃなくて卒業して院に行くか就職するかにしとけ
12 名前：名刺は切らしておりまして[sage] 投稿日：2010/08/14(土) 13:34:18 id:F96ItWIx
こういうのは検証が終わってからにして貰いたいね
１つの難問で世界中から何万通と来るのに
いちいち噂の段階で記事にされてもねえ
19 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 14:06:15 ID:7ldkEdjq
また長い証明を簡略化する作業がはじまるお
33 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 14:34:06 id:OrIF2rMl
俺も大学時代かじってた。
俺んとこは証明論(論理学)を使って証明しようてしてた。超越数学つうのかな。
結局、役に立たない定理の別証明で修了したけど。
就職して大学でやったことが全く役に立たないばかりか、誰もＮＰ問題しらなかったことに驚嘆したがな。
34 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 14:36:13 ID:VPG459jA
数学と理論科学と投資は人格破綻者でもサクセスする可能性のある稀有なフィールド
▼ 37 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 14:45:32 id:OrIF2rMl
>>34
極めて一握りの成功者以外は、社会不適合者を排出しまくりだけどね。
38 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 14:46:34 ID:BnYyJRgL
数学専攻で超頭の良い奴。
文系の俺でもよく分かるように、池上さんレベルで、いろんな例えで
説明してくれ。
いや、説明して下さい、お願いします。
▼ 45 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 15:00:42 id:VPG459jA
>>38
世界の多くの物事は一部の人たちによって数学的に説明されてきた
物事の本質を理解すれば複雑に見えることもシンプルに捉えられる場合がある
数学の公式（定理）はそのために存在していて、それは日々生まれている。
それらの本質を狙い撃ちにする道具を使えば、世界の多くの物事を数学的な
問題として形式化した場合に解答を導き出すのが楽になる。
だから数学者は存在意義がある。でも、数学者がいくら考えても
気の利いた解決方法がなさそうな問題がある。
それらは小学生でも思いつくような虱潰しなやり方しかさせてくれない。
そういう問題を集めてひとつのグループにまとめる。
で、研究次第では気の利いたやり方が見つかるような問題を集めて、
またグループをつくる。このとき、前者のグループに属している問題は
もはや質的に後者のグループに属している問題とは違っているのではないか。
それはじゃあどういう「質」の違いなんでしょうか。その説明をしてみて。
▼ 49 名前：名刺は切らしておりまして[sage] 投稿日：2010/08/14(土) 15:04:42 id:e5M8wa+n
>>38
文系の俺が将棋の手の数え上げでたとえようとして書いて面倒になったので、
以下の例文が丁度よさそうなのでこれを例示したい。
http://maname.txt-nifty.com/blog/2006/07/pnp_c7ab.html
＞ 要するにP＝NPとは「どんな問題にも一般的な解法がある」ことで、
＞ P≠NPとは「世の中には、総当たりでしらみつぶしに調べる以外に解法が存在しない問題が存在する」ことである。
＞ P≠NPであるだろうという予想から、暗号の世界でこのように活用されています（RSA暗号）。
＞ 例えば、816256193を素因数分解しろと言われたらどうします？私には小さい素数からしらみつぶしに調べることしか思いつきません。
＞ しかし、816256193＝26981×30253であると答えを示されたら、これを証明するのは非常にカンタンですね。
＞ この答えを探すためにしらみつぶしに探すしかないことを証明するか、
＞ あるいはすべての問題に対し何かしら一般的な解法を用いて答えを導くことができることを証明することができれば、
＞ １億円がもらえるのです。
▼ 58 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 15:22:43 ID:BnYyJRgL
とても親切な>>45と>>49のおかげで、今のところ、俺が理解したこと。
数学の問題には子どもみたいに虱潰しやれば解ける問題がある。それがＰ。
一方で、もっと上等な計算をして答えを出すみたいな問題がある。それがＮＰ。
で、Ｐ≠ＮＰとは、世の中の問題は上等な計算だけでは解けない問題があり、
子どもみたいに虱潰しでやらないと絶対に解けない問題がある。
これを証明してみろってことかなあ。
バカ文系の理解としては、だいたい、これであってるんでしょうか。違ってるんでしょうか。
あってるとしたら、何だかとっても興味が沸いてくるけどなあ。
▼ 59 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 15:33:17 id:VPG459jA
>>58
逆。NPが難しい方でPが上手いやり方がある方。まあ本質的なことではないけど。
で、NPっていうのは数学者的には「虱潰しをすれば解ける問題」というより
「手に負えないもの」というか、もはや脱出できない牢獄みたいな感じ。
だって虱潰しって瞬時にどんなコンピュータでも歯が立たなくなるような
組み合わせになってしまうものだから事実上解けない問題みたいなもの。
もしくは解ける範囲で我慢して、あとは近似で我慢するしかない問題。
逆に言えば実用にとっては常に近似でいいから問題はないみたい。この場合は
決定性っていって、まさにドンピシャな答えが求められる世界での話し。
あと、カオスとかの理論だと近似も無理らしいけど。
▼ 60 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 15:33:20 ID:ZWfVcQh+
>>58
２段落目は大体あってる。
１段落目は違う。人間の計算方法で説明する。
Ｐは上等な計算を駆使すれば何とかなる問題。
例えば、35*99を解くとき、3500-35を計算すれば楽に解けるような。
ＮＰは、そういう上等な計算が無い（といわれてる）問題。
例えば、23*87みたいな。これは、頑張って筆算するしかない。
そのため、問題のサイズが大きくなると、解けなくなる。
上の例なら二桁の計算なら何とかなるけど、１００桁になると無理、みたいな。
あくまで掛け算問題は例でって、
本来は、充足可能性問題とかクリーク問題とかです。
ぷよぷよ、テトリス、チョコレートパズルとかもＮＰ完全だったかな。
84 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 16:22:12 id:VPG459jA
一番本質的なことはまず、
数学的に定式化できる問題を、それを計算の立場から見たときの難しさで
分類してしまおうという態度というか方向性だと思う。
これは最初にはっきりさせたクックという人はそれだけでも歴史に残ったと思う。
まだ生きてるけど。これって多分ヒルベルトとかチューリングとかゲーデルとか
の時代に始まった野望の一部だと思うけど。なんかある全体を支配してやろう
っていう意志を感じる。リーマン予想は素数に対する支配欲だと思うし。
85 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 16:22:32 ID:ybqhpxql
こんなのどうでもいいから原子物理学のみならず宇宙法則の解明にさえ
繋がる可能性を秘めたリーマン予想をなんとかしてくれよ。
86 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 16:24:06 ID:4W0K6FZ2
うーん、たしか、五次元だか四次元だかの方程式の一般の解法がないとか、
証明されてなかったけ？
そういうのじゃダメなの？この証明って、
ほら、ここに、一般的な解法がない高次方程式ありますよ。
で、証明終了ってことじゃ？
一個でも、一般的な解法がないものを提示できたら、
証明終了のような気がするんだけど。
▼ 87 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 16:27:00 ID:ZWfVcQh+
>>86
ガロアのこと？
▼ 91 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 16:34:51 ID:4W0K6FZ2
>>87
ガロアだったかな。
３次までは方程式ならったけど、
それ以上かな、ないんだよね。で、証明されてるんだよね。
▼ 95 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 16:54:20 ID:ZWfVcQh+
>>91
アーベルが４次元の解を求めて、あとはガロアが色々と。
もうちょい厳密な定義もあるけど、確かに言うとおり、
どれも明らかに虱潰ししかなさそうな問題ではある。
そこで、虱潰し以外の探し方は本当に無いの？
無いなら証明してみてよってのが、PversusNP問題みたいなもんだ。
98 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 17:05:39 id:VPG459jA
エルミートだったかのエピソードで、円周率か自然対数の底が
超越数だってことを証明することに成功したときに、
「これを証明するのは本当に大変だった、もうこんな思いはしたくない」
みたいなことを言ったらしい。でも証明は１０枚にもみたない論文だという。
107 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 17:55:29 ID:UoLlC8L0
ポアンカレ予想を解いちゃった人みたいに、
人類が知ってはいけない領域を知ってしまって廃人になっちゃうのかなぁ・・・
113 名前：名刺は切らしておりまして 投稿日：2010/08/14(土) 18:29:30 id:FMmoMpLY
こういう難題って問題の内容自体わからない…
114 名前：名刺は切らしておりまして[] 投稿日：2010/08/14(土) 18:33:22 id:VPG459jA
>>113
時間かければそのうち分かる。テキストなりをネットで無料で見つけよう。
「証明可能性に関する証明（ゲーデル）」っていうのも革命的だったけど
「計算複雑性に関する証明」というものもあるということだと思う。
