OpenAIの「50年ぶりの理論計算機科学の快挙」は、宇宙の原子数より小さい閾値まで指数時間だった
Efficient algorithms, the Exponential Time Hypothesis, and losing the plot
OpenAIが発表した充足可能性問題の「準指数時間」アルゴリズムは、理論計算機科学における50年ぶりの大発見として話題になった。しかし実際には、変数が10^10,000,000,000,000,000,000,000,000未満の場合は指数時間の全探索を行う。宇宙の原子数は約10^80なので、実質的にあらゆる問題で指数時間だ。効率性の定義そのものの欠陥を浮き彫りにしている。
このほとんど有限とも言えない閾値までは、魔法の新アルゴリズムは指数時間のサブルーチンを呼び出す。我々が考慮し得るあらゆる問題にとって、その手続きは指数時間なのである。
HNでの議論
49- inkysigma
時間計算量解析の実用性に対する批判はかなり見てきたが、それを何に置き換えるべきかを説明した記事は見たことがない。与えられた時間計算量解析は、不完全であっても問題の無限の動物園にいくらかの構造を与え、比較的うまく合成でき、比較的単純だ。また扱いやすく、数学的構造を持ち、しばしばヒューリスティックとして実用的でもある（人が通常遭遇したり思いついたりするアルゴリズムの種類は、この種の解析の下ではたいてい妥当だ）。適切な代替となるには、これらすべての性質を満たす必要がある。そのような代替がなければ、問題とその複雑さを何の枠組みもなしに分析することに戻ってしまい、ときどきbig Oが実用的でないことを覚えておくだけよりもさらに悪いように思える。
私が知る限り、より実用的な唯一の候補はキャッシュオブリビアスアルゴリズムのためのキャッシュ複雑性だが、それははるかに複雑だ。
- simiones
この著者は複雑性理論と、それがどのように重要かを本当に誤解しているようだ。指数関数＝悪、多項式＝善という選択は当初はほぼ恣意的だったかもしれないが、それ以来ずっと堅固な基盤を見出している。
指数関数的複雑性は、アルゴリズムが「可能な解を生成し、正しいか検証し、正しくなければ繰り返す」ものであるときに自動的に得られるものだ。多項式複雑性は、問題自体に何らかの構造があり、それを利用して直接解を構築するか、あるいは（問題サイズに対して）非常に小さな、手作業でチェックすべき可能な解の集合を生成できるときに得られるものだ。
さて、あらゆる実用的な問題解決の目的において、「P = NPだが、n^10^80以上の時間を要するアルゴリズム（しかもこれが典型的なケースでも証明された下限であり、改善の見込みはない）でのみ成り立つ」は「P != NP」とまったく等価だろう。しかしそれでも、数学的には極めて興味深い結果であり、解が正しいか検証するのが容易なあらゆる問題には、解の生成を「容易」にする何らかの隠れた構造が伴うことを教えてくれる。そして、最悪ケースは同じように手に負えないままだとしても、今日知られていない、実際に容易なインスタンスの新しいサブクラスを見つける扉を開く可能性もある。
さて、AIが見つけた新しいアルゴリズムによるETHの反証はそれほど印象的ではないことに注意してほしい。それほど深い含意があるようには思えない。準指数[…]
- emil-lp
ETHについて：今では多くの人が、ETHは単に強すぎる形で述べられていたのであり、正しい指数時間仮説はSH、すなわち充足可能性仮説だと言っている。
それはETHとほぼ同じだが、指数における多項式を超える改善を許す（これがClause/ChatGptによって証明されたことだ）。
おすすめの文献：
- throwaway713
「私は超有限主義者だ」と言うためのとても回りくどい言い方だな…
- QuesnayJr
これは著者の持論へのまた別の愚痴だ。
NP完全問題に対して銀河的でない多項式時間アルゴリズムが存在するか否かを証明できれば素晴らしい。しかし我々は、銀河的多項式時間アルゴリズムが存在するか否かを証明するという、より易しい問題すら解けていないのに、より難しい問題に何の望みがあるというのか？
NP問題に対する任意の多項式時間アルゴリズムが銀河的でなければならないと証明できれば、あなたはTuring以来最も称賛される計算機科学者になるだろう。ただ、誰もその方法を思いつかないだけだ。