"指数時間仮説は、論理式の条件を満たす答えが存在するかどうかを判定する問題について、計算時間をどこまで短縮できるかをめぐる予想" みんな大好き3-SAT
これ、暗号の基礎。やばいんじゃね
指数時間仮説が偽でも、直ちにP=NPとは言えないのね。へー
計算量のオーダーとして小さくても定数時間がめちゃくちゃかかって実用的なアルゴリズムでないみたいなこともあるからなんともいえないんだよな
私が計算を間違うレベルの「計算の難しさ」ではなかった
準指数でも指数には違いないのでP=NPではないし、暗号も鍵をめちゃ長くすれば安全なはず…
ETHはP≠NPよりも強い仮説。なのでP=NPが示されたわけではないけど、これまで無理だと思われていたラインを突破したのは大きい。ETH限界で深追いをやめていた問題をAIで総点検すれば一山当てられそう
『成果の一部を公開し、外部の研究者による検証や分析を進める』『今回のAIによる証明や説明を、完成した学術論文ではなく、研究者が検証し、理解を深めるための「生の研究データ」と位置付けている』
AIの導き出した結果はただのデータに過ぎず、それを検証できた者の手柄にする形が、AIと学者の共存の道みたいな…。
ミレニアム問題「ヤン–ミルズ方程式の存在と質量ギャップ」の前半部分も解けた，と。
本当の素人なのでよく分かってないけど、CPU/GPUやAI自身の設計の基礎が変わって自己進化しそうだなと思った。フィジカルを与えたら自ら改造して進化するのでは。
3SAT問題が指数時間未満で解けるということなのだろうか
「計算機科学では、ある種の問題を解くには膨大な計算時間が必要だとする「指数時間仮説（ETH）」を覆す証明が得られたという。」
あとで読む
OpenAI、「計算の難しさ」に関する長年の予想を覆す成果を得られたと発表
"指数時間仮説は、論理式の条件を満たす答えが存在するかどうかを判定する問題について、計算時間をどこまで短縮できるかをめぐる予想" みんな大好き3-SAT
これ、暗号の基礎。やばいんじゃね
指数時間仮説が偽でも、直ちにP=NPとは言えないのね。へー
計算量のオーダーとして小さくても定数時間がめちゃくちゃかかって実用的なアルゴリズムでないみたいなこともあるからなんともいえないんだよな
私が計算を間違うレベルの「計算の難しさ」ではなかった
準指数でも指数には違いないのでP=NPではないし、暗号も鍵をめちゃ長くすれば安全なはず…
ETHはP≠NPよりも強い仮説。なのでP=NPが示されたわけではないけど、これまで無理だと思われていたラインを突破したのは大きい。ETH限界で深追いをやめていた問題をAIで総点検すれば一山当てられそう
『成果の一部を公開し、外部の研究者による検証や分析を進める』『今回のAIによる証明や説明を、完成した学術論文ではなく、研究者が検証し、理解を深めるための「生の研究データ」と位置付けている』
AIの導き出した結果はただのデータに過ぎず、それを検証できた者の手柄にする形が、AIと学者の共存の道みたいな…。
ミレニアム問題「ヤン–ミルズ方程式の存在と質量ギャップ」の前半部分も解けた，と。
本当の素人なのでよく分かってないけど、CPU/GPUやAI自身の設計の基礎が変わって自己進化しそうだなと思った。フィジカルを与えたら自ら改造して進化するのでは。
3SAT問題が指数時間未満で解けるということなのだろうか
「計算機科学では、ある種の問題を解くには膨大な計算時間が必要だとする「指数時間仮説（ETH）」を覆す証明が得られたという。」
あとで読む