OpenAIのモデルが、古典的な論理パズルに対してより高速な解法を発見し、指数時間仮説（ETH）を否定した。機械検証済みの証明がこの主張を裏付けており、27年間研究者が信頼してきた前提を覆した。
今回の成果は、現代暗号の根幹にある「P=NP」問題を証明するものではない。そのため、このアルゴリズムがビットコイン（BTC）やイーサリアムの暗号技術に直接影響を与えることはない。
指数時間仮説はなぜ重要だったか
この仮説は、真偽値のスイッチとそれらを結ぶ規則からなる「3-SAT」というパズルに関するもの。目的は、すべての規則を同時に満たすスイッチの設定を見つけること。
提案された解の検証は容易だが、解を見つけるのは難しい。なぜならスイッチが1つ増えるごとに組み合わせが倍増するからである。
ラッセル・インパリアッツォ氏とラマモハン・パトゥリ氏は1999年にETHを提案した。ただし、この略称はイーサリアムのティッカーとは無関係である。
この仮説は、最悪の場合においていかなるアルゴリズムもこの指数的な成長を回避できないと主張するもの。
研究者はこれを不可欠な前提条件として扱ってきた。OpenAIによれば、グラフ理論、計算生物学、データベース分野で数百本の論文がこの仮説を基盤に困難性証明を構築している。
AIはいかにして専門家の見落とした近道を発見したのか
OpenAIのシステムは10月16日に自然言語による証明を作成した。翌日、チームはこれをLeanという論理的ステップすべてを検証するソフトウェアで形式化した。
公開されたアルゴリズムは、変数n個の入力をおよそ2の(n/√log n)乗のステップで処理する。これはETHが想定した指数時間を下回るが、実用的な速度にはほど遠い。
OpenAIは、実用レベルでの高速化にはさらなる研究が必要であると注意を促している。
インパリアッツォ氏とパトゥリ氏（ともにカリフォルニア大学サンディエゴ校）は、MITのライアン・ウィリアムズ氏とともに今後レビューを主導する。つまり、仮説の提唱者自身がその反証を検証する構図となる。
一方でOpenAIは、今回の発見について科学的功績を主張しない姿勢を示している。これは以前のナビエ・ストークス方程式の論争を踏まえたもの。
テキサス大学オースティン校のコンピューターサイエンス教授、スコット・アーロンソン氏はこのニュースを聞いた様子を語った。
「私の学生らがオフィスにやって来て、OpenAIのモデルが指数時間仮説を否定したと伝えてくれた」
スコット・アーロンソン氏 Shtetl-Optimizedより
ETHの反証はP=NPを意味するのか
違う。P対NP問題は、迅速に検証できる解を持つ全問題が、迅速に解けるかどうかを問うものである。
ETHはP≠NPよりも強い主張であり、これが否定されてもより大きな疑問は依然として未解決のまま残る。
谷間を隔てる山脈を想像すると、AIは稜線越えの近道を見つけたが、トンネルを貫通させたわけではない。
OpenAIのグレッグ・ブロックマン社長兼共同創業者も、発表の数時間後に同様の見解を示した。
この違いは暗号資産保有者にも重要である。ビットコインの署名は楕円曲線暗号に依存しているが、今回のアルゴリズムはこの難問には触れていない。
BeInCryptoのマーケットインテリジェンス・エキスパート評議会のメンバー、ベンジャミン・カウエン氏はこうした懸念について言及した。
ただし明確にしておきたいのは、指数時間仮説の否定はP=NPの証明にはならず、ビットコインやイーサリアムの安全性が損なわれるものでもない。
指数時間仮説：機械が創造者を上回る時に何が起きるか
不可能とされてきた前提が覆された前例は過去にもある。1960年にはアナトリー・カラツーバ氏が、アンドレイ・コルモゴロフ氏の乗算に関する予想をわずか約1週間で否定した。
同様にボルカー・シュトラッセン氏は1969年、標準的な行列乗算こそが最適であることを示そうとしたが、より高速な手法を発見した。
今回異なるのは、近道を発見するのが誰かという点にある。機械が証明を生み出し、人間がその解釈に努めている。
同じ発表では、調和解析や素粒子物理学に関するさらなる証明も示された。
こうした動きはデジタル資産にも影響を及ぼす。暗号学者マシュー・グリーン氏は、AIがウォレットの背後にある数学を弱体化させる可能性についてすでに警鐘を鳴らした。
カウエン氏はこの教訓を市場の観点から述べた。同氏の見解では、金融から遠く離れた分野もやがて市場を変革し得る。
困難性の仮定に支えられた業界にとって、AIの各種ブレークスルーは、今やストレステストの役割も兼ねている。
