アカウント名:
パスワード:
P=NP のほうが色々と役立つし
もう20年来、否定の予想で専門家の間では定着しているから、今さら肯定的結論では、そちらの方が大混乱だよ。セキュリティ関連への悪影響と最適化問題への有用性だと、今はもう悪影響の方が大きいんじゃないかな。
商用化へ加速、量子コンピューター「9000兆倍の破壊力」 [nikkei.com]あたりを見ると、だいぶ盛っているにしても稼動するようになってから一般に使えるようになるまでの間は数理的な証明如何に寄らず「量子コンピュータを使える組織にとっては暗号は解ける物」って状態が不可避に思えますね。# 暗号方式と運用で何とかなる方法、あるのかな。。。
量子アニーリング式と量子ゲート式の区別すらついてないクソ記事なんぞ読むにも値しない
(肯定的に)証明できても、解が直ちにわかるわけじゃないから、どうってことない気もするが。
自分の名前をパスワードにしても直ちに破られる訳ではないからどうってことないと言っているほどに、おめでたい。
そうでもないんだ。数学の歴史を紐解くと酷い事例が結構ある。
数学者A「○○できる方法が存在することを証明しました」←この証明はちょっと基礎知識があれば簡単に理解出来る数学者A「え? その方法の実例? 存在するとは言ったけど具体的なやり方は知らんがな」
-長い年月-
数学者Z「ついにそのアルゴリズムの実例を見つけました!」←とてもじゃないけど理解不能
数学者Aのその発見から新たな分野ができあがり、そんな考え方もあるのか、いっちょやったろかと突っ込んでった無数の数学者が死屍累々した後で、ようやく解決するというパターン。ああいう天才は天才なので、一番美味しい所だけちょこっと持って行って放置しよる、と先輩が泣いてた。
有名どころでは、シャノンの通信路符号化定理 [wikipedia.org]とか。
こちらのほうが長いから、こっちに返事つけますが、具体的アルゴリズムが得られてないってのは、P=NPがわかっているのに比べてはるかに時間の問題だと思うのだけど。まさにパスワードと生年月日の問題くらいに。具体的アルゴリズムの多項式の次数が高いってのは、お話にならないくらい本質的に時間の問題だよな。
純粋数学と違って対象のつかみどころは割りとはっきりしているから、P=NPの証明ができたら、アルゴリズムに関する知見もかなりあると見るのが妥当。もしくは、P=NPどころではない何かすごいものを見つけて証明しているかになる。その場合は、まあ、私の言っていることは外れることになるけど、そのときはこんな議論どうでもよいほど面白い世界に変わるから、私はそっちにいく。
うん、まあ、証明されるとしたら、その「P=NPどころではない何かすごいもの」方面になると思うんだ。さくさく実用出来るようなアルゴリズムが実在するようなら、もう既にP=NPは証明されてるだろうし。
SFネタとしてはさくさく暗号解読できるアルゴリズムが見つかる方が好きだけどね。
存在証明はされているけど具体的な特定は不可能って数学ではよくあるから"時間の問題"で片付くほど簡単には思えないけどな。それにもし手続きが見つかったとしても、O(n^グラハム数)とかでしょどうせ。素数判定のO(n^7.5)ですら実用にならんしそうそう都合良くはいかない。(面白い世界になってほしいというのは同意だが)
ちなみにシャノン限界は、計算量理論だと計算時間の下界と同じようなもんで、下界の計算時間のアルゴリズムを見つける＝タイトバウンドを見つけるのは難しい問題。P=NPの場合は、それ自身がタイトバウンドを見つけたイメージになる。
話の本質が分かってないね。
P=NPであることと、NP問題を多項式時間で解く方法が具体的に得られることと、そのアルゴリズムが現実的なレベルのオーダーであることは全部別だよね
P=NPは決定問題なので、直ぐに何かが起こるという結論の間には実は、ギャップがある。
P=NPである、というのは、おなじみの巡回セールスマン問題で言うと、「全長x未満の経路はある?」にYes/Noの解を求めるアルゴリズムが存在する、と言う意味。直ぐに分かることとして、2分探索をすれば、「最短の経路長は?」という問題も解ける。
ただ、「最短の経路を求めよ」という問題はまた別。
「もしも」の話をするなら、「P=NP」が証明された上で、「最短の経路を求めよ」の方は多項式オーダーでは解けないと証明される、という超展開もあり得る。
「P!=NP」→「最適化問題問題の方も解けない」、とか、「最適化問題が解けた」→「P=NP」とかは真なので、「どうせP!=NPなんだからそこまで深く考えなくても」とスルーされがちだけど。
査読なしだと、エイプリルフール的なネタ論文の可能性もある。
多分そうじゃないの？本気で正しいと思ってるなら、査読付きで権威のある論文誌に投稿すんでしょ。＃「再昇華チオチモリンの吸時性」を読み返したくなった。
> 査読付きで権威のある論文誌に投稿すんでしょ。たまに変人がいるみたい
https://ja.wikipedia.org/wiki/ArXiv#.E3.83.9D.E3.82.A2.E3.83.B3.E3.82.... [wikipedia.org]
そんな奇人変人列伝の一人に挙げられそうな例を出されても…# しかし得てして天才数学者は変人だから困る
まあ、せっかく公開されている論文を自分でチェックできるような知力がなくて、周辺であれこれ言ってる程度なら黙って専門家の判断を待ってるのが吉ですね。
体裁を整えるには大変な手間がかかるし査読も数年かかることがあるからとりあえずarXivに投稿するのは不思議ではない
ちなみに "The P-versus-NP page" には査読付きの論文もあるので査読は意外とあてにならないらしい
らしいってーか「無いよりマシ」程度なのはみんな分かってるよ。それでも「無いトコのは眉に余計にツバつけとけ」って評価は変わらない。
数学とか計算機科学の論文は記号論理学的な記述にコンパイル可能なフォーマットで提出を義務付ければ定理検証は容易にできるはずだからそういう形になればいいのに。AIによる機械学習にも使えるし、在野の自称数学家でも普通に提出できるし。
査読なんて社会学的で不確かな手法は時代遅れになるべきだ。
それで、コンパイラの脆弱性をついて任意コード実行が可能になる論文がポストされる、と……
そしてコードの査読をするんですね。わかります。
それは人間がする必要が無いから良いだろ。
節子、それ新規性ない。ただの恒等式や
SSL(の秘匿性を前提とした電子商取引)やブロックチェーンは死亡だしNSAや中国やロシアは大歓喜だしね。
いやいやあらゆる数学の証明がパソコンを数時間とか(+-数十桁)回せば自動で可能になるだけで大きな魅力だと思わないか？アルゴリズムも解の満たす条件を記述するだけで十二分になるんだよ。TASとかも超簡単。
暗号化なんてのは量子暗号やワンタイムパッドが全てを解決するよ多分。
通りすがりコメですが、
もしも、解決したら、その関係者達が知れ渡ったら、某競馬場やラスベガスとかでヤサグレている方々の視線が飛んできそうですね。そしてその歴史的瞬間をTV視聴してみたいと思います。
P=NPが証明されてからの顛末を小説にしたら絶対楽しいだろうなと思ったけど、そんな小説はすでにあるらしい。これ [amazon.co.jp]。読んだ事はないけど、とにかくすごく楽しい事が起きるのは間違いないと思う。暗号の崩壊を含めてね。
それ、amazon のアフィリエイトつきリンクでは。意図的にやっているならやめてほしいし(amazon アフィリエイトの規約違反)、ミスなら気を付けてほしい。
検索したら他でも貼りまくってるから意図的だろ
以前紹介したときのリンクをコピペしたのでミスです。すみません。sradは消せないので厄介ですね。ただ、ACで書き込んでいる時は特定されたくはありません。間違って埋め込まれた時に変に指摘しないで欲しいです。こっちじゃなくてAmazon側にでも通報すれば向こう側で適切に対処するでしょう。
同じ間違いを他のサイトでも繰り返さないように，コピペ用のリンクを今すぐに書き換えておくといいかも．ところで通報ってやったことないからわからないんですが，あなたが間違いですって報告するのは駄目なんですか?
他には一件しかないはずです。そちらのコピペです。ここ以外に二件以上あるなら第三者によるものです。閲覧数的にまずないと思います。意図的でない点は説明した通りですし、今までアフィリエイト収入が発生したことはありません。必要ならAmazon側にメールなどで問い合わせていただいても構いません。
コピペ元のリンクは別サイトの物でAmazonアソシエイトの利用規約に則ったもの…だと思います。性質上書き換えられません。こんな事書いたなと思ってざっと漁っただけです。sradにはダイレクトメッセージのような機能はないので不特定多数に知らせずに私に依頼する事はできません。
ま、次回以降は「https://www.amazon.co.jp/exec/obidos/ASIN/453578728X/」って感じで後半をカットして載せるこったな
指数が十分に小さければそうだけど、太陽系の寿命で収まるようなオーダーになるとは思えない
その認識はNSAや各国の諜報機関に役割や立場について誤解している。彼らは保守的で現状の破滅的な変化を望まない。制限付きで暗号の安全性が担保されている現状が一番都合が良い。自分たちが暗号を自由にできるということは自分らも安全に暗号を使うことができないということ。つまり誰も得をしない。
たとえP=NPでも、どうせものすごく次数の高い多項式オーダーだったりするでしょうから、実用上は大して関係ないです。どんなNP完全問題も2次オーダーで済むというなら話は別ですが……
すみません、すでに住人です。もう MakeGirls.moe も試しました……
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
ソースを見ろ -- ある4桁UID
間違いであってほしい (スコア:0)
P=NP のほうが色々と役立つし
Re:間違いであってほしい (スコア:1)
もう20年来、否定の予想で専門家の間では定着しているから、
今さら肯定的結論では、そちらの方が大混乱だよ。
セキュリティ関連への悪影響と最適化問題への有用性だと、今はもう
悪影響の方が大きいんじゃないかな。
Re:間違いであってほしい (スコア:2)
商用化へ加速、量子コンピューター「9000兆倍の破壊力」 [nikkei.com]
あたりを見ると、だいぶ盛っているにしても稼動するようになってから一般に使えるようになるまでの間は数理的な証明如何に寄らず「量子コンピュータを使える組織にとっては暗号は解ける物」って状態が不可避に思えますね。
# 暗号方式と運用で何とかなる方法、あるのかな。。。
Re: (スコア:0)
量子アニーリング式と量子ゲート式の区別すらついてないクソ記事なんぞ読むにも値しない
Re: (スコア:0)
(肯定的に)証明できても、解が直ちにわかるわけじゃないから、どうってことない気もするが。
Re: (スコア:0)
自分の名前をパスワードにしても直ちに破られる訳ではないから
どうってことないと言っているほどに、おめでたい。
Re:間違いであってほしい (スコア:1)
そうでもないんだ。数学の歴史を紐解くと酷い事例が結構ある。
数学者A「○○できる方法が存在することを証明しました」←この証明はちょっと基礎知識があれば簡単に理解出来る
数学者A「え? その方法の実例? 存在するとは言ったけど具体的なやり方は知らんがな」
-長い年月-
数学者Z「ついにそのアルゴリズムの実例を見つけました!」←とてもじゃないけど理解不能
数学者Aのその発見から新たな分野ができあがり、そんな考え方もあるのか、
いっちょやったろかと突っ込んでった無数の数学者が死屍累々した後で、ようやく解決するというパターン。
ああいう天才は天才なので、一番美味しい所だけちょこっと持って行って放置しよる、と先輩が泣いてた。
有名どころでは、シャノンの通信路符号化定理 [wikipedia.org]とか。
Re: (スコア:0)
こちらのほうが長いから、こっちに返事つけますが、
具体的アルゴリズムが得られてないってのは、P=NPがわかっているのに比べて
はるかに時間の問題だと思うのだけど。
まさにパスワードと生年月日の問題くらいに。
具体的アルゴリズムの多項式の次数が高いってのは、お話にならないくらい本質的に
時間の問題だよな。
純粋数学と違って対象のつかみどころは割りとはっきりしているから、
P=NPの証明ができたら、アルゴリズムに関する知見もかなりあると見るのが妥当。
もしくは、P=NPどころではない何かすごいものを見つけて証明しているかになる。
その場合は、まあ、私の言っていることは外れることになるけど、そのときは
こんな議論どうでもよいほど面白い世界に変わるから、私はそっちにいく。
Re: (スコア:0)
うん、まあ、証明されるとしたら、その「P=NPどころではない何かすごいもの」方面になると思うんだ。
さくさく実用出来るようなアルゴリズムが実在するようなら、もう既にP=NPは証明されてるだろうし。
SFネタとしてはさくさく暗号解読できるアルゴリズムが見つかる方が好きだけどね。
Re: (スコア:0)
存在証明はされているけど具体的な特定は不可能って数学ではよくあるから
"時間の問題"で片付くほど簡単には思えないけどな。
それにもし手続きが見つかったとしても、O(n^グラハム数)とかでしょどうせ。
素数判定のO(n^7.5)ですら実用にならんしそうそう都合良くはいかない。(面白い世界になってほしいというのは同意だが)
Re: (スコア:0)
ちなみにシャノン限界は、計算量理論だと計算時間の下界と同じようなもんで、
下界の計算時間のアルゴリズムを見つける＝タイトバウンドを見つけるのは
難しい問題。
P=NPの場合は、それ自身がタイトバウンドを見つけたイメージになる。
Re: (スコア:0)
話の本質が分かってないね。
Re: (スコア:0)
P=NPであることと、NP問題を多項式時間で解く方法が具体的に得られることと、そのアルゴリズムが現実的なレベルのオーダーであることは全部別だよね
Re: (スコア:0)
P=NPは決定問題なので、直ぐに何かが起こるという結論の間には実は、ギャップがある。
P=NPである、というのは、おなじみの巡回セールスマン問題で言うと、「全長x未満の経路はある?」にYes/Noの解を求めるアルゴリズムが存在する、と言う意味。直ぐに分かることとして、2分探索をすれば、「最短の経路長は?」という問題も解ける。
ただ、「最短の経路を求めよ」という問題はまた別。
「もしも」の話をするなら、「P=NP」が証明された上で、「最短の経路を求めよ」の方は多項式オーダーでは解けないと証明される、という超展開もあり得る。
「P!=NP」→「最適化問題問題の方も解けない」、とか、「最適化問題が解けた」→「P=NP」とかは真なので、「どうせP!=NPなんだからそこまで深く考えなくても」とスルーされがちだけど。
Re: (スコア:0)
査読なしだと、エイプリルフール的なネタ論文の可能性もある。
多分そうじゃないの？本気で正しいと思ってるなら、査読付きで権威のある論文誌に投稿すんでしょ。
＃「再昇華チオチモリンの吸時性」を読み返したくなった。
Re: (スコア:0)
> 査読付きで権威のある論文誌に投稿すんでしょ。
たまに変人がいるみたい
https://ja.wikipedia.org/wiki/ArXiv#.E3.83.9D.E3.82.A2.E3.83.B3.E3.82.... [wikipedia.org]
Re: (スコア:0)
そんな奇人変人列伝の一人に挙げられそうな例を出されても…
# しかし得てして天才数学者は変人だから困る
Re: (スコア:0)
まあ、せっかく公開されている論文を自分でチェックできるような知力がなくて、周辺であれこれ言ってる程度なら黙って専門家の判断を待ってるのが吉ですね。
Re: (スコア:0)
体裁を整えるには大変な手間がかかるし査読も数年かかることがあるからとりあえずarXivに投稿するのは不思議ではない
Re: (スコア:0)
ちなみに "The P-versus-NP page" には査読付きの論文もあるので査読は意外とあてにならないらしい
Re: (スコア:0)
らしいってーか「無いよりマシ」程度なのはみんな分かってるよ。
それでも「無いトコのは眉に余計にツバつけとけ」って評価は変わらない。
Re: (スコア:0)
数学とか計算機科学の論文は記号論理学的な記述にコンパイル可能なフォーマットで提出を義務付ければ定理検証は容易にできるはずだからそういう形になればいいのに。
AIによる機械学習にも使えるし、在野の自称数学家でも普通に提出できるし。
査読なんて社会学的で不確かな手法は時代遅れになるべきだ。
Re:間違いであってほしい (スコア:1)
それで、コンパイラの脆弱性をついて任意コード実行が可能になる論文がポストされる、と……
Re: (スコア:0)
そしてコードの査読をするんですね。わかります。
Re: (スコア:0)
それは人間がする必要が無いから良いだろ。
Re: (スコア:0)
節子、それ新規性ない。ただの恒等式や
テロリスト視点かな? (スコア:0)
SSL(の秘匿性を前提とした電子商取引)やブロックチェーンは死亡だしNSAや中国やロシアは大歓喜だしね。
Re: (スコア:0)
いやいやあらゆる数学の証明がパソコンを数時間とか(+-数十桁)回せば自動で可能になるだけで大きな魅力だと思わないか？
アルゴリズムも解の満たす条件を記述するだけで十二分になるんだよ。TASとかも超簡単。
暗号化なんてのは量子暗号やワンタイムパッドが全てを解決するよ多分。
Re: (スコア:0)
通りすがりコメですが、
もしも、
解決したら、その関係者達が知れ渡ったら、某競馬場やラスベガスとかでヤサグレている方々の視線が飛んできそうですね。
そしてその歴史的瞬間をTV視聴してみたいと思います。
Re: (スコア:0)
P=NPが証明されてからの顛末を小説にしたら絶対楽しいだろうなと思ったけど、そんな小説はすでにあるらしい。
これ [amazon.co.jp]。
読んだ事はないけど、とにかくすごく楽しい事が起きるのは間違いないと思う。暗号の崩壊を含めてね。
Re: (スコア:0)
それ、amazon のアフィリエイトつきリンクでは。意図的にやっているならやめてほしいし(amazon アフィリエイトの規約違反)、ミスなら気を付けてほしい。
Re: (スコア:0)
検索したら他でも貼りまくってるから意図的だろ
Re: (スコア:0)
以前紹介したときのリンクをコピペしたのでミスです。すみません。
sradは消せないので厄介ですね。
ただ、ACで書き込んでいる時は特定されたくはありません。間違って埋め込まれた時に変に指摘しないで欲しいです。
こっちじゃなくてAmazon側にでも通報すれば向こう側で適切に対処するでしょう。
Re: (スコア:0)
同じ間違いを他のサイトでも繰り返さないように，コピペ用のリンクを今すぐに書き換えておくといいかも．
ところで通報ってやったことないからわからないんですが，あなたが間違いですって報告するのは駄目なんですか?
Re: (スコア:0)
他には一件しかないはずです。そちらのコピペです。
ここ以外に二件以上あるなら第三者によるものです。閲覧数的にまずないと思います。
意図的でない点は説明した通りですし、今までアフィリエイト収入が発生したことはありません。
必要ならAmazon側にメールなどで問い合わせていただいても構いません。
Re: (スコア:0)
コピペ元のリンクは別サイトの物でAmazonアソシエイトの利用規約に則ったもの…だと思います。性質上書き換えられません。
こんな事書いたなと思ってざっと漁っただけです。
sradにはダイレクトメッセージのような機能はないので不特定多数に知らせずに私に依頼する事はできません。
Re: (スコア:0)
ま、次回以降は「https://www.amazon.co.jp/exec/obidos/ASIN/453578728X/」って感じで
後半をカットして載せるこったな
Re: (スコア:0)
指数が十分に小さければそうだけど、太陽系の寿命で収まるようなオーダーになるとは思えない
Re: (スコア:0)
その認識はNSAや各国の諜報機関に役割や立場について誤解している。
彼らは保守的で現状の破滅的な変化を望まない。
制限付きで暗号の安全性が担保されている現状が一番都合が良い。
自分たちが暗号を自由にできるということは自分らも安全に暗号を使うことができないということ。
つまり誰も得をしない。
Re: (スコア:0)
たとえP=NPでも、どうせものすごく次数の高い多項式オーダーだったりするでしょうから、実用上は大して関係ないです。
どんなNP完全問題も2次オーダーで済むというなら話は別ですが……
Re:間違いであってほしい (スコア:1)
Re: (スコア:0)
すみません、すでに住人です。もう MakeGirls.moe も試しました……