X
トップページ⇒数学
447コメント132KB
P vs NP
■ このスレッドは過去ログ倉庫に格納されています
0146１３２人目の素数さん
垢版 |
2017/05/31(水) 19:52:34.74ID:0qbtak2u
>>133
SATだったら変数に真か偽か入れてはプログラムを動かせば、変数の数の回数だけ動かして、一つの解が求まる。
クソ遅い方はどうなんだろう。
素数判定は6乗位だったと思うけど実装されて、使われているのかな？
0147１３２人目の素数さん
垢版 |
2017/06/01(木) 01:30:33.14ID:nBxIGcKX
>>146
示されている方法でSATを解くと、
組み合わせ分を試すわけなので指数オーダーになるよ。
AKS素数判定法での計算量は (Wikiによると) \tild{O}(log(n)^7.5) っぽい。
でも、実際には使われてないだろうなー
0158１３２人目の素数さん
垢版 |
2017/06/02(金) 17:42:11.15ID:bfJzN9YC
P≠NP問題は大多数の数学者が研究している現代数学の本流（代数、解析、幾何）からは遠く離れた辺境（計算機科学）で生まれた問題で
現在でも、研究が進んで道具立てが整備されている数学の本流とは結びついていないので難しい（難問に立ち向かうための道具が
貧弱な状態で取り組まねばならないということ）

リーマン仮説は現代数学の本流中の本流でこの問題に取り組むための道具（つまり理論）の整備を長年に亘って膨大な数学者が整備し
続けてきたが今もって全く歯が立たないという意味で本当に難しい問題

言い換えると、P≠NP問題は、それが本当にどのぐらい難しい問題なのか（しばらく前に300年余りぶりに解決されたフェルマーの大予想ほどなのか、
それよりは易しそうなのか、難しそうなのか）ということが評価できない（難しさを評価できるほど数学に組み込まれていない）という意味で難しい
少なくとも、様々な道具を揃えて多くの数学者が取り組んでいるリーマン仮説へのチャレンジに比べれば、P≠NP問題へのチャレンジは
手探りと呼んでも良いようなレベル

例えばコラッツ予想（与えられた正の整数が偶数の時は２で割り、奇数の時は３を掛けて１を足すというのを繰り返せばいつかは１になるという予想）は
実に簡単な問題に見えるが解決されないままだし、解決の見通しも今の時点では全く立っていないはず
この問題がどのぐらい難しいのかの評価も全く不明のまま

P≠NP問題は計算機科学の大問題なので非常に多くの理論計算機科学者は取り組んでいるが、現代数学の本流とは未だに繋がっておらず
その難しさが現代数学が持っている道具立てに基づいて評価できないという意味では、少し乱暴な言い方だが、コラッツ予想に似ている

フェルマーの大予想を解決したWilesさんがかつて述べていたが、フェルマーの大予想も数学の本流とは結びついていなかった（あの大予想を
解決しようとしてKummerの理想数のアイデアを整理し正当化しようという努力から代数的整数論が誕生したにもかかわらず）が、Faltingsによって
あの大予想が楕円曲線に関する谷山−志村予想と結びついたことによって現代数学（の、この投稿で言ってる意味での、本流）と結びつき位置付けられて
現代数学の問題としてどうチャレンジすべきかが見えて来た、とね
0160１３２人目の素数さん
垢版 |
2017/06/03(土) 08:55:44.87ID:FbuAHE0y
>159
頭わるくてすまん
「"p-selectable" np complete」でぐぐったがわからんかった
説明してくれるとありがたいのだが
0161１３２人目の素数さん
垢版 |
2017/06/03(土) 09:29:55.55ID:FbuAHE0y
>>158
同意っす

計算複雑性理論界隈の人たちの多くは、チューリングマシンや記号論理学あたりにいるっぽい。
計算モデルとして回路計算量が提案されたあたりから少し広がりは出たけど、
数学のメインストリームとは繋がりが薄い。
多くの計算量クラスを生み続けている気がする...

一方、NP完全問題とグラフ問題は親和性が高くて、
入力されるグラフを限定することで多項式時間で解けるアルゴリズムを見つけてる。
グラフ理論もまた、数学のメインストリームとは繋がりが薄い。
グラフを代数的に扱う分野はあるが、かなりマイナーである。

これらとは違う方向として、アルゴリズマーな方々は探索問題の枝刈り頑張ってて、
「(実用上は)多項式時間」というのも叩き出してたりするんだけど、
計算実験は証明じゃないしね..

ということで、現代数学の本流との架け橋を繋げられれば道は開けるのかなと。
0162161
垢版 |
2017/06/03(土) 09:39:53.50ID:FbuAHE0y
業界的には手詰まり感が漂ってる気がする
ブレークスルーが必要なんだけど、だれも本気で分野間に橋をかけようとしてない気がする
そういう試みは業界的には無視の方向なのかもしれない

まあ、計算理論やるより、コンピュータ業界に就職する方がお金を稼げそうなので、
新しい人も入ってこないんかもね
0173１３２人目の素数さん
垢版 |
2017/06/12(月) 16:24:00.33ID:3ur0Moka
マンハッタン計画（日本人大量虐殺実験）に携わった科学者
ユダヤ系に★をつけると

ロバート・オッペンハイマー★ ニールス・ボーア★
エンリコ・フェルミ 　　ジョン・フォン・ノイマン★
オットー・フリッシュ★ エミリオ・セグレ★ ハンス・ベーテ★
エドワード・テラー★ ユージン・ウィグナー★ スタニスワフ・ウラム★
ハロルド・ユーリー★ ジェームズ・フランク★ リチャード・ファインマン★
etc.
0174１３２人目の素数さん
垢版 |
2017/06/12(月) 16:31:36.40ID:3ur0Moka
ロスト・イン・トランスレーションはコッポラの娘のソフィア・コッポラ監督作品で２００３年のアカデミー賞を総なめにした
東京を舞台にした孤独な白人同士の交流を描いた作品だが、この映画は白人女が日本女をどうみていたのがよく描かれている。
マンコしかとりえがない猿のような設定だ。白人女と日本女の交流は全く描かれていない
この映画は若い頃にモデルとして来日してたキャメロン・ディアスも描かれている。キャメロン・ディアスは日本を相当嫌っていたようで
日本人の知り合いは全く出てこない。ホテルでしか酒を飲まない。
日本人のいる居酒屋は全く出てこない。白人女が日本人をどう観ていたのかよく判る傑作だぜ
0175１３２人目の素数さん
垢版 |
2017/06/12(月) 16:32:57.83ID:3ur0Moka
ロスト・イン・トランスレーションは日本女の評判がすこぶる悪かった
あの映画は「白人女が日本女をどう見ていたのか」が強烈に描かれている
まさにイエローキャブ、マンコ猿のような設定だぜｗ日本男は主に軽薄なヤンキーとして描かれている。藤井隆だ
あの映画を観た時に日本に滞在している白人ですら日本人は猿にしか見えないと考えていると思ったね
0176￥ ◆2VB8wsVUoo
垢版 |
2017/06/12(月) 16:54:15.42ID:Lt75QqGT
■■■馬鹿板をスルと菅官房長官みたいな嘘吐きになります。そやし止めなさい。■■■

￥
0187１３２人目の素数さん
垢版 |
2017/06/12(月) 23:27:31.96ID:wX/ODItS
>>158
NSは数学でも数理物理でも物理でも、重要命題かつ計算機が発達してるのに
やっぱり無理じゃないか‥‥
となってるので、とんでもなく難しいんだろうね
0188１３２人目の素数さん
垢版 |
2017/06/13(火) 15:01:47.38ID:/URkUpsU
>>59
人工知能てDLのこと？
あれの実装面で発展してるのはCNNであって、細かなミスの許される画像認識に関しては強いけど
他に関しては全然だ
0201１３２人目の素数さん
垢版 |
2017/08/15(火) 19:23:24.35ID:thmGAPfN
ついに証明されたぞー
https://arxiv.org/abs/1708.03486

A Solution of the P versus NP Problem

Norbert Blum
(Submitted on 11 Aug 2017)
Berg and Ulfberg and Amano and Maruoka have used CNF-DNF-approximators to prove
exponential lower bounds for the monotone network complexity of the clique function and of
Andreev's function. We show that these approximators can be used to prove the same
lower bound for their non-monotone network complexity. This implies P not equal NP.
0212１３２人目の素数さん
垢版 |
2017/08/16(水) 01:06:31.87ID:jEeCkROO
>>201
> ついに証明されたぞー

凄い！
この証明が正しければ、想像してたよりも色んな意味であっけなく片が付いたというのが正直な個人的感想です
それはともかく、これが正しいならば、P≠NPという形で解決したということは多項式時間階層も潰れないから、
計算量理論屋さんにとって時間計算量クラスの間の等不等に関する未解決問題は無数に残っているので
失業の心配も当分は不要ということになる
0223１３２人目の素数さん
垢版 |
2017/08/17(木) 17:59:53.52ID:jtkTJYdp
>>201
これとは全く独立だけど同じ時期にHPのパロアルト研究所の研究員のVinay Deolalikarが
１日だけプレプリントを彼のホームページに公開して「証明した」って発表して
しかも計算量の大家にしてTuring賞受賞者のStephan Cookが「まともそう」ってお墨付きを与えたものだから
大騒ぎになったけど、結局、どうも間違ってるって結論になったみたいですね
（この騒ぎのお蔭で彼の名前でオランダ語版のWikipediaにページが作られたみたいだ）

● この騒ぎに関する記事（の日本語訳…どうも翻訳の質は高くないらしい）：　

http://jp.techcrunch.com/2010/08/13/20100812fuzzy-math/

● Vinay Deolalikarのプレプリント（2010年の日付になっているので温めていたのかも）のオランダのサイトにミラーされたもの（？）

https://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf


Blumがarxivにアップすることで証明を発表したので、Deolalikarは証明の先取権を主張するためにずっと温めていたのを
あわてて発表したと推察すべきかも知れない（そう推察すると、Deolalikarのプレプリントが2010年であるにもかかわらず
発表のタイミングはDeolalikarのほうが３日ほど遅い13日になったのも自然な説明がつく）
0224１３２人目の素数さん
垢版 |
2017/08/17(木) 23:29:31.57ID:eEGidgoV
>>201
査読は通ってるん?
内容について、だれか解説してくんろー
0235１３２人目の素数さん
垢版 |
2017/08/18(金) 14:46:00.86ID:VqSR3OPH
>>224
> 査読は通ってるん?

査読には時間がかかる（通常の平凡な論文でも数ヶ月から長ければ半年以上も要する）ので
取り敢えずarxivに登録して公開し証明の先取権の争いが起こった際に必要となる内容・日時の証拠を確保した段階
これから学術雑誌に投稿して査読を受ける（あるいは既に投稿済で査読中という）ことになる
0237１３２人目の素数さん
垢版 |
2017/08/18(金) 19:38:01.81ID:VqSR3OPH
>>236
> なんか矛盾あるみたいね

？？？
Blumのプレプリントに間違いがあるってこと？
それとも私の235の投稿の内容に何か間違いがあるの？
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況