効率的なアルゴリズム、指数時間仮説、そして論点の見失い

Galactus the Devourer

［画像: Galactusのイラスト］

こんにちは、argmin読者の皆さん！今日の投稿は、計算機科学における効率性を厳密に定義しようとして失敗してきた歴史についてです。以前のフーリエ変換に関する投稿と同様に、いつものより技術的な内容ですが、できるだけ分かりやすくしようと努めました。

私は、応用数学の実践におけるこの有害なパターンに常々魅了されてきました。これは数週間前にこちらの記事で書いたものです。

応用数学者は、問題を解決するために巨大な数学的モデリングの足場を築く必要があることがよくあります。この足場は、元の問題とは直接関係のない新しい数学的なパズルを生み出し、問題解決者を惹きつけます。そして、それらのパズルを解決する何十もの追随論文を目にすることになりますが、そもそも私たちが気にかけていた問題を忘れてしまっています。

このような「忘れ」の最も良い例は、計算量理論の分野でしょう。

1965年、Jack Edmondsは、グラフの最大マッチングを見つけるための巧妙な方法を考案しました。彼は、自分のアルゴリズムが「効率的に」計算できると主張したかったのです。なぜなら、その手順は少し複雑で、実行にはコンピュータが必要だったからです。しかし、彼はアルゴリズムが効率的であるとはどういうことかを記述する言語がないことに気づきました。彼の論文のセクション2、「Digression（脱線）」と名付けられた箇所で、彼はこう書いています。

辞書によれば、「efficient（効率的）」とは「操作または性能において十分である」という意味です。これは私が望む意味に近いでしょう。なぜなら、最大マッチングに効率的なアルゴリズムが存在しない可能性も考えられるからです。おそらく、より良い言葉は「good（良い）」でしょう。

私は、数学的な結果として、良いアルゴリズムの存在を主張します。

Edmondsは、マッチング問題の可能なすべての解を列挙し、最大のものを探し出すことができると指摘しました。これは正しいアルゴリズムですが、可能なマッチングの総数はグラフのサイズに対して指数関数的に大きくなります。すべての可能なマッチングを盲目的に書き出し、最大のものを選ぶというのは「良くない」アルゴリズムです。それは「悪い」アルゴリズムと呼べるでしょう。彼の新しい手順は、はるかに効率的でした。

そこでEdmondsは、良いアルゴリズムの定義を構築するために2ページを費やしました。彼は、問題サイズについて、誰もが合理的な定義に合意することを要求しました。彼のマッチング問題では、サイズはグラフの頂点の数と辺の数であるとしました。そして、良いアルゴリズムとは、問題のインスタンスがいかに大きくても、そのサイズのある定義された関数によって実行時間が上限されるものであるとしました。彼は、実行時間の制限が考えられるすべてのサイズに対して成り立つことを要求しました。なぜなら、誰かが少数の小さなインスタンスに意図的に難しいものを仕掛けることで問題を操作するかもしれないと恐れたからです。

Edmondsはこの定義に完全に満足していたわけではありませんでした。実際、彼はこう書いています。

厳格な基準が、知られていない、あるいは基準にうまく適合しないことが知られているアルゴリズムの実用的な開発を阻害するのは不幸なことです。今日知られている最高のアルゴリズム的アイデアの多くは、そのような理論的な pedantry（難解さ）によって損なわれるでしょう。実際、際立った未解決の問題は、本質的には「どの程度良い」のかということです。線形計画法におけるシンプレックス法のアルゴリズムは？そして一方で、電気スイッチング理論における多くの重要なアルゴリズム的アイデアは、明らかに我々の意味での「良い」ものではありません。1

この注意書きを添えて、彼は脱線を締めくくり、新しいブロッサムアルゴリズムの計算量を発表しました。「マッチングアルゴリズムの困難さの上限は n^4 です。ここで n はグラフの頂点の数です。」

Edmondsは、「良い」という意味についてそれ以上の議論をしませんでした。彼は、指数時間（exponential time）は悪いと断言しました。ほとんどのアルゴリズム設計者にとって、入力長に比例する線形時間（linear time）は、当然ながら優れていました。さらに、我々の小学校の掛け算アルゴリズムは二次時間（quadratic time）を要しました（学校で習ったように手計算で2つの3桁の数を掛け合わせ、計算で書き出す桁数を数えてみてください）。そしてそれはかなり良いように思えました。Edmondsは、4次の操作数を必要とするマッチングアルゴリズムを持っていました。Richard Karpのような後の形式主義者たちにとって、多項式時間（polynomial time）の操作数は、良さの合理的な定義のように思えました。多項式時間は良い。指数時間は悪い。これが計算量理論の分野を創設し、あらゆる種類のアルゴリズムが多項式時間で実行されることを証明し、多項式時間アルゴリズムが存在しない問題の特性を明らかにすることを目標としました。

しかし、多項式時間はおそらくEdmondsを悩ませたでしょう。技術的には多項式であっても、n^1000 のようにスケールする手順は「良い」アルゴリズムではありません。さらに不条理なことに、

［画像: y = x^1000 と y = 2^x のグラフ］

は、私たちが遭遇する可能性のあるどんな n に対しても、指数関数 2^n より大きい多項式です。多項式は常に「良い」の不完全な定義でしたが、私たちはそれを使ってきました。数千本の論文の後、私たちは計算の現実から切り離された、混乱した計算量結果の動物園を持っているだけです。

実際、多項式と指数の違いを漸近的に考えることは、「銀河系規模のアルゴリズム（galactic algorithms）」を設計するという悪い習慣を可能にします。これは、私たちの宇宙では決して実装できないほど実行時間が大きい概念的な手順です。私は以前のOpenAIの高速フーリエ変換に関する投稿でこれらに言及しました。

ここで、OpenAIの親切な友人たちに戻りましょう。今週、彼らは理論計算機科学における最新のブレークスルーを発表しました。彼らは、充足可能性問題（satisfiability problem）に対して「準指数時間（subexponential time）」で実行されるアルゴリズムを提供しました。充足可能性問題は最もよく知られた「NP完全問題」の一つであり、今日はP対NPの問題の詳細には立ち入りたくありませんが、充足可能性問題に対する多項式時間アルゴリズムを見つけることができれば、クレイ数学研究所のミレニアム賞を獲得できると言えば十分でしょう。2

さて、準指数時間とは多項式時間のことではありません。それは単に、実行時間が次のように上限されることを意味します。

［画像: f(n) = 2^(n^c) のような準指数時間のグラフ］

ここで n は問題サイズであり、f は「劣線形（sublinear）」関数です。つまり、n が無限大に近づくにつれて f(n)/n の極限がゼロになることを意味します。

実際、OpenAIの充足可能性問題に対する新しいアルゴリズムの場合、その上限は次のようになります。

［画像: f(n) = 2^(n^(1/d)) のような準指数時間のグラフ］

ある指定されていない定数 d と C に対して。この式は醜いですが、これはTwitterで50年間で理論計算機科学における最大の瞬間として宣伝されました。今週、テックプレス全体で報道されました。OpenAIは明らかに、これが「big fucking deal（とてつもなくすごいこと）」だと私たちに思わせたかったのです。そして多くの理論計算機科学者がソーシャルメディアで同意しました。

それが非常に大きな出来事だったので、アルゴリズムを少しでも理解できるか見てみました。もちろん、皆さんに伝えてきたように、私たちはこれらの論文を読むべきではありません。ChatGPTに何が書いてあるか尋ねるべきなのです。そしてChatGPTは、落とし穴があると言いました。

導出されたアルゴリズムは、変数の数が 10^10,000,000,000,000,000,000,000,000 未満の場合、Edmondsが1965年に悪いと断言した網羅的探索（exhaustive search）を実行します。

これは完全に理解不能な数です。3 宇宙には約 10^80 個の原子があります。これはそれよりも 10^9,999,999,999,999,999,999,999,920 倍小さいのです。このかろうじて有限な閾値までの間、魔法のような新しいアルゴリズムは指数時間サブルーチンを呼び出します。私たちが ever（常に）考慮できるどんな問題に対しても、その手順は指数時間です。「結果」は、奇妙で、知ることのできない無限の近傍でのみ、充足可能性問題が準指数時間で解決されるということです。

充足可能性問題に対する主張された準指数時間アルゴリズムは、私たちの効率性の定義が50年前よりもさらに悪かったことの決定的な証拠です。その答えは、効率性や良さについては何も教えてくれません。時には、自分の質問に答えることで、自分が何か別のものを求めていたことに気づくことがあります。

私は賭け事はしませんが、予測があります。P=NPが何らかの銀河系規模の意味で成り立つことが判明し、私たちが学んだすべては、50年間間違った質問に答えてきたということになるでしょう。

1

Edmondsがここでシンプレックスアルゴリズムに言及しているのは面白いです。シンプレックスアルゴリズムは史上最も重要なアルゴリズムであり、技術的にはその実行時間は指数関数的であることがわかっています。ほとんどの場合、それは高速ですが、指数関数的なステップを要する奇妙なケースを構築することができます。それにもかかわらず、それは世界中で展開されており、最適化における指数関数的に多様なアプリケーションの最適なプログラムを決定しています。Edmondsは1965年に理論と実践のこの鋭い断絶を予見していました！

2

特に皮肉なのは、産業規模の充足可能性問題に対処するための信じられないほど効率的なアルゴリズムが存在することです。従来のコンピュータは、数百万の変数と数百万の節を持つ問題を解決できます。この人物は、Intelで10億個の変数と40億個の節を持つ問題を1日で解決しました。

3

私はこのクレイジーな数を、論文をClaudeに読み込ませて確認しました。ChatGPTとClaudeはお互いを嫌っているので、もし彼らが同意するなら、それは真実でなければなりません。