X
トップページ⇒数学
447コメント132KB
P vs NP
■ このスレッドは過去ログ倉庫に格納されています
0038１３２人目の素数さん
垢版 |
2014/03/23(日) 12:49:49.80
P vs NP問題を解決するとされている、「消滅解」って、
具体的にどういうものか知っている人いますか。
0041１３２人目の素数さん
垢版 |
2014/03/24(月) 04:34:23.24
山口人生氏の本を読んだけど、本に記されている記述が不十分なのか、私の理解力が不十分なのか分りませんが、
読んでも結局分りませんでした。
0043１３２人目の素数さん
垢版 |
2014/05/16(金) 00:49:05.73
PvsNPってイエスかノーで答えられる判定問題だけを扱うんだよね
P=NPだとしたらRSA暗号が簡単に解読できる方法があることになるからヤバいって話をよく聞くけど、ある数の素因数を求めよって問題は判定問題じゃないから、PやNPとは何も関係ないんじゃね？
0044１３２人目の素数さん
垢版 |
2014/05/21(水) 19:53:56.05
>>43
NがM未満の素因数を持つか？っていう決定問題がPだと、二分探索をその桁数のオーダーだけやれば解けちゃうよ
0046１３２人目の素数さん
垢版 |
2014/08/06(水) 10:19:33.62
P/NP=N^(-1)
0048１３２人目の素数さん
垢版 |
2015/03/20(金) 10:33:57.64ID:Ipb9fO2f
みきやん予想

ある位数nの群全てを多項式時間で見つけ出すアルゴリズムは存在する
0049１３２人目の素数さん
垢版 |
2015/03/22(日) 11:31:03.48ID:puQMCwvC
すみません、計算機屋のみきやんですけど反応ください
0050１３２人目の素数さん
垢版 |
2015/03/22(日) 19:44:40.59ID:puQMCwvC
改定

みきやん予想

任意の位数nの群全てを多項式時間で見つけ出すアルゴリズムは存在する
0051１３２人目の素数さん
垢版 |
2015/11/26(木) 14:50:34.17ID:2eAh2Qsb
NP≠Pを証明するのってなんでそんなに難しいの？
0053１３２人目の素数さん
垢版 |
2015/11/26(木) 22:29:26.84ID:zhCidC09
P ≠ NP を自力で証明することと
P ≠ NP 予想を誰かが解決したあとにその照明の内容を理解することはどちらが難しいか？
0054１３２人目の素数さん
垢版 |
2015/11/26(木) 23:45:39.43ID:QsskYz9S
入門書読むと、コンピュータ科学最大の難問の一つである、とか証明の努力を退けてきた、とか
いろいろ書いてあるけど、どういう試みがなされたのかとか証明につながるヒントとか
可能性がたかそうなルートとか研究の中途の説明ってないんだよねえ
誰か教えてよ
進展具合とか、もうみんな諦めちゃって手がついていないのか？
0057１３２人目の素数さん
垢版 |
2015/11/27(金) 08:59:02.08ID:d59IPEdm
まあ、俺以外の誰かだと500年くらい掛かりそうだが、俺なら200年で出来る気がするな
人生短いから、実証出来ないのが残念
0058１３２人目の素数さん
垢版 |
2015/11/27(金) 23:26:50.82ID:yXKZ7T4I
自力で証明する方が証明のチェックより難しいというのは
まさにP ≠ NP的な話だね
0059１３２人目の素数さん
垢版 |
2015/11/30(月) 20:41:22.80ID:SStpBv11
人工知能にNP問題学習させたら多項式時間で解けるようなったりして。
0063１３２人目の素数さん
垢版 |
2015/11/30(月) 23:54:07.65ID:SStpBv11
TSPの都市配置と最短経路を学習データとして
ディープラーニングで学習させたら良い解返してくれるんじゃないか。
0065１３２人目の素数さん
垢版 |
2015/12/01(火) 18:56:35.23ID:B3VaAOp4
CNFと充足解を学習データとして
ディープラーニングで学習させたらSATが多項式時間で解けるようになるかも

まあSATは無理でも素因数分解とかなら良い線いくんちゃう？
0066１３２人目の素数さん
垢版 |
2015/12/02(水) 09:03:58.81ID:uGobi9Ry
どうでもいい与太話も結構だが、君は「解ける」の意味をちゃんと理解してから書き込むように
0067１３２人目の素数さん
垢版 |
2015/12/11(金) 23:48:54.04ID:y8CRtoTw
導出原理なかなか楽しい。
鳩ノ巣原理なんかは時間かかるらしいが。
0068１３２人目の素数さん
垢版 |
2015/12/28(月) 17:02:51.40ID:f9D4SFuA
すまん、だれか教えてくれ
http://www.ti.inf.ethz.ch/ew/lehre/extremal04/raemy.pdf
これなんだが。

なぜサイズmの鳩ノ巣原理のレゾリューションの証明の中に
m^2/9個の変数を持つクローズが出てくることが言えると、
鳩ノ巣原理の証明長が指数になることが言えるの？
m^2/9個の変数を持つクローズが全部出てくるの？
0069１３２人目の素数さん
垢版 |
2016/02/15(月) 03:36:11.05ID:8JYeZ3jx
記述計算量において、
Pは「最小不動点演算子を持つ一階述語論理」で、
NPは「存在量化二階述語論理」であらわされる。
「最小不動点演算子を持つ一階述語論理」の無矛盾性を
「存在量化二階述語論理」で証明できれば、
ゲーデルの第二不完全性定理より、
「最小不動点演算子を持つ一階述語論理」より
「存在量化二階述語論理」が大きいと言えるから、
P≠NPも言えるのではないか。
この証明、どうだろう？
0071１３２人目の素数さん
垢版 |
2016/02/21(日) 01:13:18.21ID:l/2Y/c0/
述語論理の公理系の規則が全てトートロジーである事から証明できると思います。
0072１３２人目の素数さん
垢版 |
2016/05/13(金) 20:27:09.69ID:BegVM+5s
たとえばP vs NP が連続体仮説の結果に依存するとかいう可能性はあるの？
0073１３２人目の素数さん
垢版 |
2016/05/13(金) 21:59:07.26ID:BegVM+5s
あるいはビジービーバーみたいにＮＰを多項式で解くアルゴリズムは存在することはするけど、
どのアルゴリズムがそれかは絶対わからないとか。
0075１３２人目の素数さん
垢版 |
2016/10/08(土) 01:36:08.57ID:uDpf+4BC
俺が証明したらフィールズ賞くれるの？
0097１３２人目の素数さん
垢版 |
2017/05/14(日) 11:51:51.33ID:6zDFiTmB
いきなりすまん。
解けたけど、(自分以外)だれも理解できないっぼい。
ペレルマンさんの気持ちがわかる気がする。
0098１３２人目の素数さん
垢版 |
2017/05/14(日) 11:56:23.33ID:6zDFiTmB
フィールズ賞もらえる歳は超えちまった。
ちなみに、フィールズ賞(ノーベル賞もだけど)は税金がかからんが、
クレイ研究所が提示してる方は免除の記載が無いらしいので、
このままだと半分が税金。
0109１３２人目の素数さん
垢版 |
2017/05/14(日) 12:32:18.46ID:lg6ZUYhf
>>97-98
人生２世さん乙〜ｗ　（人生さんはあの第２巻は出さず終いなんだろうなあｗ）

P vs NP問題を解決した場合、もらえるのはフィールズ賞（純粋数学）じゃなくてネヴァンリンナ賞（理論計算機科学）だ
ちなみに年齢制限に関しては超えていても本当に解決したのならば特別賞が与えらえるだろうね
フェルマー大予想を解決したワイルズさんも（受賞時でなく）解決時に既に40歳の制限を超えていたがICM 1998でフィールズ賞の特別賞を受賞した
年齢制限はフィールズ賞を授与するICMの前年中に40歳に達していたらＮＧとのこと
011097
垢版 |
2017/05/14(日) 12:47:57.84ID:6zDFiTmB
>>109
れすありがと。人生さんいたね。懐かしー
んで、ネヴァンリンナ賞なんですね。情報ありがとう。
ちなみに年齢制限は余裕で超えてるw
011197
垢版 |
2017/05/14(日) 12:54:23.47ID:6zDFiTmB
他の最近の研究動向調べてて思ったんだけど、この問題って、人気なさ気だなと。
しかも、一般的にも認知度が低い。リーマン問題さんがうらやましいww
0122１３２人目の素数さん
垢版 |
2017/05/15(月) 03:23:33.41ID:9zy0+xIM
>>111
知名度は低いかも知れませんけど
応用範囲の広さは随一でしょう
もっともP≠NPの可能性が高いですから
能率的なアルゴリズムが生まれるのではないですが
暗号の安全性という意味ではP≠NPが望ましい結果です
0133１３２人目の素数さん
垢版 |
2017/05/20(土) 12:21:03.73ID:QqOpEWlW
NP完全問題をPで解けるアルゴリズムがある(だがその方法で最適解が求まる訳では無い)、とか、Pではあるんだが、O(n^10000) とかだったらどう？
0134１３２人目の素数さん
垢版 |
2017/05/20(土) 12:32:23.80ID:x8e1GjEa
>>133
前者は解けるとは言わない。近似解アルゴリズムならいくらでも手抜きできる
後者はそのままだと困難だけど改良の余地がある
0135１３２人目の素数さん
垢版 |
2017/05/20(土) 17:34:56.02ID:dtYVrowk
>>133 例えば背理法を用いて、P \neq NP を仮定して矛盾を示したとする。
(背理法で解けるという主張では無く、あくまで例です)

この時、存在は示されてたものの、
具体的に解を求めるアルゴリズムは示されて無いので、
実用性の面では役に立たない。

存在証明だけで凄い事ではあるんだろうけど。
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況