アルゴリズムにとって、記憶は時間よりもはるかに強力なリソースである

この物語 のオリジナル版はQuanta Magazineに掲載されました。

2024年7月のある午後、ライアン・ウィリアムズは自らの誤りを証明しようと試みた。コンピューティングにおける時間と記憶の関係について、驚くべき発見をしてから2ヶ月が経っていた。それは、記憶がコンピュータ科学者が考えていた以上に強力であることを示す数学的証明のラフスケッチだった。考えられるあらゆる計算において、少量の記憶でも大量の時間と同じくらい役に立つのだ。あまりにもあり得ない話に聞こえたので、彼は何かが間違っているに違いないと確信し、すぐに証明を脇に置いて、もっと突飛でないアイデアに集中した。そして今、ついに誤りを見つけるための時間を確保したのだ。

しかし、実際にはそうではありませんでした。何時間もかけて自分の主張を吟味したにもかかわらず、ウィリアムズは一つも欠点を見つけられませんでした。

「気が狂いそうだと思ったんです」と、マサチューセッツ工科大学の理論計算機科学者であるウィリアムズは語った。彼は初めて、もしかしたら、記憶は自分の研究が示唆するほど強力なのかもしれないという可能性を抱き始めた。

その後数ヶ月にわたり、彼は細部を詰め込み、あらゆるステップを精査し、他の研究者数名からのフィードバックを募りました。そして2月、ついにその証明をオンラインで公開し、大きな称賛を浴びました。

「驚きです。素晴らしいです」と、ニュージャージー州プリンストン高等研究所の理論計算機科学者、アヴィ・ウィグダーソン氏は語った。このニュースを聞くとすぐに、ウィグダーソン氏はウィリアムズ氏に祝福のメールを送った。件名は「驚きました」だった。

時間とメモリ（空間とも呼ばれる）は、計算における最も基本的な2つのリソースです。あらゆるアルゴリズムは実行に時間がかかり、実行中にデータを保存するための空間も必要です。これまで、特定のタスクを実行するためのアルゴリズムは、実行時間にほぼ比例する量の空間を必要としていました。研究者たちは長い間、これより優れた方法はないと考えていました。ウィリアムズの証明は、あらゆるアルゴリズム（その動作に関わらず）を、はるかに少ない空間を使用する形式に変換する数学的手順を確立しました。

さらに、この結果（ある量の空間が与えられた場合に何が計算できるかという記述）は、ある量の時間では何が計算できないかという第二の結果も示唆している。この第二の結果自体は驚くべきものではない。研究者たちはそれが真実だと予想していたものの、それをどのように証明すればいいのか分からなかったのだ。ウィリアムズの解決策は、最初の包括的な結果に基づくもので、まるで漫画のように過剰に感じられる。まるで地球上の他の全員に鉄壁のアリバイを証明して、容疑者の有罪を証明するかのようだ。これは、コンピュータサイエンスにおける最も古い未解決問題の一つに挑む新たな方法を提供する可能性もある。

「これは実に驚くべき成果であり、大きな進歩です」とワシントン大学のコンピューター科学者、ポール・ビーム氏は述べた。「ライアンがこれをやったというのは、少し驚きが薄れましたね。」

歩き回れるスペース

46歳のウィリアムズ氏は、表情豊かで開放的な顔立ちで、髪にはほんのりと白髪が混じっている。MITステイタ・センターのカラフルな尖塔を見下ろす彼のオフィスは、空間の創造的な活用を如実に示している。窓辺はヨガマット2枚で即席の読書コーナーに生まれ変わり、机は奇妙な形の隅に押し込められ、数学的な落書きで埋め尽くされた大きなホワイトボードに面したソファを置くスペースが確保されている。

ウィリアムズ氏が幼少期を過ごしたアラバマ州の田舎町からは、MITは遠く離れている。そこには広大な土地が広がっていた。50エーカーの農場で育ったウィリアムズ氏は、7歳の時に初めてコンピューターを目にした。母親に連れられて郡を横断し、特別学習クラスに通った時のことだ。彼は、デジタル花火を生成するシンプルなプログラムに魅了されたことを覚えている。

「ランダムな色をモニターの中央からランダムな方向に送るんです」とウィリアムズは言った。「どんな画像が出てくるかなんて、予想もつかなかった」。コンピューターの世界は、無限の可能性に満ちた、ワイルドで素晴らしい遊び場のようだった。若きウィリアムズはすっかり夢中になった。

「将来のコンピューターで動くプログラムを、紙に書いていました」と彼は言った。「両親は僕をどう扱えばいいのか、本当に分からなかったんです。」

成長するにつれ、ウィリアムズは空想上のコンピューターから現実のコンピューターへと進んでいきました。高校最後の2年間は、名門公立寄宿学校であるアラバマ数学・科学学校に転校し、そこで初めてコンピューターサイエンスの理論的な側面に触れました。

「世の中にはもっと広い世界があり、コンピューターを数学的に考える方法があることに気づきました」と彼は言った。「それが私がやりたかったことだったんです。」

ウィリアムズは、理論計算機科学の分野である計算複雑性理論に特に興味を持ちました。この分野は、リストのソートや因数分解といった計算問題を解くために必要なリソース（時間や空間など）を扱います。ほとんどの問題は、それぞれ異なる時間と空間の要求を持つ、多くの異なるアルゴリズムによって解くことができます。複雑性理論家は、問題を最も効率的に解くアルゴリズム、つまり最も高速に実行されるアルゴリズムや最も少ない空間を使用するアルゴリズムのリソース要求に基づいて、複雑性クラスと呼ばれるカテゴリに分類します。

しかし、計算資源の研究を数学的に厳密にするにはどうすればよいでしょうか？時間と空間を、分単位とメガバイト単位を比較して分析しようとしても、あまり進展しません。何らかの進歩を遂げるには、正しい定義から始める必要があります。

機知に富む

これらの定義は、限られた資源でやりくりしてきた経験を持つコンピュータ科学者の先駆者、ユリス・ハートマニスの研究から生まれました。彼は1928年にラトビアの名家家庭に生まれましたが、第二次世界大戦の勃発により幼少期は混乱に陥りました。ソ連占領軍は彼の父親を逮捕・処刑し、戦後、ハートマニスは難民キャンプで高校を卒業しました。大学に進学し、教科書を買う余裕がなかったにもかかわらず、優秀な成績を収めました。

「講義では詳細なメモを取ることでそれを補っていました」と彼は2009年のインタビューで回想している。「即興で困難を乗り越えることには、ある種の強みがあるのです」。ハートマニスは1949年にアメリカに移住し、カンザスシティ大学で数学を学びながら、農業機械の製造、鉄鋼製造、さらには執事など、様々な雑用をこなした。そして、当時まだ若かった理論計算機科学の分野で、華々しいキャリアを築いた。

1960年、ニューヨーク州スケネクタディにあるゼネラル・エレクトリック社の研究所で働いていたハートマニスは、夏季インターンシップに参加していた大学院生のリチャード・スターンズと出会った。二人は画期的な論文を発表し、時間と空間の正確な数学的定義を確立した。これらの定義は、研究者たちに二つの資源を比較し、問題を複雑性のクラスに分類するために必要な言語を与えた。

最も重要なクラスの1つは「P」という控えめな名前で呼ばれています。大まかに言えば、これは妥当な時間内に解決できるすべての問題を包含します。宇宙における同様の複雑性クラスは「PSPACE」と呼ばれています。

これら2つのクラスの関係は、複雑性理論における中心的な問いの一つです。P に含まれるすべての問題は PSPACE にも存在します。なぜなら、高速アルゴリズムはコンピュータのメモリ空間を埋め尽くすほどの時間的余裕がないからです。逆のことも真であれば、2つのクラスは同等になります。つまり、空間と時間は同等の計算能力を持つことになります。しかし、複雑性理論家たちは、PSPACE は P に含まれない多くの問題を含む、はるかに大きなクラスであると考えています。言い換えれば、彼らは空間が時間よりもはるかに強力な計算資源であると考えています。この考えは、アルゴリズムは同じ小さなメモリ領域を何度も使用できるのに対し、時間はそれほど寛容ではないという事実、つまり一度過ぎてしまったら取り戻すことができないという事実に由来しています。

「直感的にとてもシンプルです」とウィリアムズ氏は言う。「空間は再利用できます。でも、時間は再利用できないんです。」

しかし、複雑性理論家にとって直感だけでは不十分です。彼らは厳密な証明を求めています。PSPACEがPより大きいことを証明するには、研究者はPSPACE内のいくつかの問題に対して、高速アルゴリズムが根本的に不可能であることを示さなければなりません。一体どこから始めればいいのでしょうか？

宇宙の旅

偶然にも、彼らはコーネル大学で研究を始めました。ハートマニスは1965年に新設されたコンピュータサイエンス学部の学部長に就任しました。彼のリーダーシップの下、同学部は急速に複雑性理論の研究の中心地となり、1970年代初頭には、ジョン・ホップクロフトとヴォルフガング・パウルという二人の研究者が、時間と空間の正確な関連性を確立しようと試みました。

ホップクロフトとポールは、P対PSPACE問題を解決するには、限られた時間内で特定の計算を実行できないことを証明する必要があることを知っていました。しかし、それが不可能であることを証明するのは困難です。そこで彼らは、問題を逆転させ、限られた空間で何ができるかを探ることにしました。彼らは、一定の空間予算を与えられたアルゴリズムが、わずかに長い時間予算を与えられたアルゴリズムと同じ問題をすべて解決できることを証明しようと考えました。これは、空間が時間よりも少なくともわずかに強力であることを示すものであり、PSPACEがPよりも大きいことを示すための、小さいながらも必要な一歩でした。

その目標を念頭に、彼らは複雑性理論家がシミュレーションと呼ぶ手法に着目しました。これは、既存のアルゴリズムを、同じ問題を解くものの、必要な空間と時間が異なる新しいアルゴリズムに変換するというものです。基本的な考え方を理解するために、本棚をアルファベット順に並べるための高速アルゴリズムが与えられたものの、本を何十もの小さな山に分けなければならない状況を想像してみてください。たとえ時間はかかっても、アパートのスペースをあまり取らない方法を好むかもしれません。シミュレーションとは、より適切なアルゴリズムを得るために使用できる数学的手順です。元のアルゴリズムを入力すると、時間はかかりますが、スペースを節約できる新しいアルゴリズムが得られます。

アルゴリズム設計者は、ソートなどの特定のタスクにおけるこうした空間と時間のトレードオフを長年研究してきました。しかし、時間と空間の一般的な関係を確立するためには、ホップクロフトとポールはより包括的なもの、つまり、どのような問題を解くかに関わらず、あらゆるアルゴリズムに機能する、空間を節約するシミュレーション手順が必要でした。彼らは、この汎用性にはコストがかかると予想していました。普遍的なシミュレーションでは、特定の問題の詳細を活用できないため、特化したシミュレーションほど空間を節約できない可能性が高いからです。しかし、ホップクロフトとポールが研究を始めた当時、空間を節約するための普遍的な手法は全く知られていませんでした。たとえわずかな節約でも、進歩となるはずでした。

画期的な進歩は1975年、ホップクロフトとポールがレスリー・ヴァリアントという若い研究者とチームを組んだ後に訪れました。3人は、常にわずかなメモリ容量を節約できる汎用的なシミュレーション手順を考案しました。どのようなアルゴリズムを適用しても、元のアルゴリズムの時間予算よりもわずかに少ないメモリ容量で、同等のシミュレーション結果が得られます。

「長い時間でできることは、少しだけ短い空間でもできる」とヴァリアント氏は語った。これは、空間と時間を繋げる探求における最初の大きな一歩だった。

しかしその後、進歩は停滞し、複雑性理論家たちは根本的な壁にぶつかったのではないかと疑い始めました。問題はまさに、ホップクロフト、ポール、そしてヴァリアントによるシミュレーションの普遍性にありました。多くの問題は時間よりもはるかに少ない空間で解くことができますが、直感的に時間と同じくらいの空間が必要になると思われる問題もありました。もしそうなら、より空間効率の高い普遍的なシミュレーションは不可能でしょう。ポールと他の二人の研究者はすぐに、一見明白な仮定を前提とすれば、それらは確かに不可能であることを証明しました。それは、異なるデータチャンクが同時にメモリ内の同じ空間を占有することはできないという仮定です。

「誰もが、これ以上のことはできないと当然思っていた」とウィグダーソン氏は語った。

ポールの結果は、P対PSPACE問題を解決するには、シミュレーションを完全に放棄し、別のアプローチを採用する必要があることを示唆していましたが、誰も良いアイデアを持っていませんでした。問題は50年間、そこで停滞していましたが、ウィリアムズがついにこの行き詰まりを打破しました。

まず、彼は大学を卒業しなければなりませんでした。

複雑度クラス

1996年、ウィリアムズは大学出願の時期を迎えました。複雑性理論を追求するには故郷を遠く離れなければならないことは分かっていましたが、両親は西海岸やカナダは論外だと明言しました。残された選択肢の中で、彼の好きな分野の歴史において重要な位置を占めるコーネル大学が際立っていました。

「ハートマニスという男が時間と空間の計算量クラスを定義したんだ」と彼は当時を思い出しながら思った。「あれは私にとって重要なことだった。」

ウィリアムズは寛大な奨学金を得てコーネル大学に入学し、1997年秋に入学した。彼は、複雑性理論家になるためなら何でもしようと心に決めていた。彼のひたむきな姿勢は、同級生たちの間で際立っていた。

「彼はとにかく複雑性理論に夢中だった」と、コーネル大学でウィリアムズと同期だったテキサス大学オースティン校のコンピューター科学者、スコット・アーロンソンは言う。

しかし2年生になると、ウィリアムズは直感よりも数学的な厳密さを重視する授業についていくのに苦労するようになった。計算理論の授業で凡庸な成績を取った後、先生は彼に他の職業を考えるよう勧めた。しかし、ウィリアムズは夢を諦めなかった。彼はさらに努力を重ね、大学院の理論講座を受講した。より難しい授業で優秀な成績を収めれば、大学院出願書類に好印象を与えられると考えたのだ。その大学院講座を担当していた教授は、当時その分野の重鎮だったハートマニスだった。

ウィリアムズはハートマニス教授のオフィスアワーに毎週出席するようになり、出席する学生はほぼ彼一人だった。彼の粘り強さは報われ、彼はその科目でAを取得し、ハートマニス教授は次の学期の独立研究プロジェクトの指導を引き受けた。二人の毎週のミーティングはウィリアムズが大学に在学する間ずっと続いた。ハートマニス教授は複雑性研究への独自のアプローチを育むよう促し、行き詰まりに陥らないよう優しく導いてくれた。

「当時、私は彼に深く影響を受けました」とウィリアムズは言った。「今もそうだと思います」

しかし、全米科学財団から切望されていた大学院研究フェローシップを獲得したにもかかわらず、ウィリアムズは応募したすべての博士課程から不合格となった。その知らせを聞いたハートマニスは同僚に電話をかけ、その後、ウィリアムズがコーネル大学の1年間の修士課程に合格したことを祝福した。1年後、ウィリアムズは再び様々な博士課程に応募し、その研究経験を糧に成功を収めた。

ウィリアムズは大学院時代もその後も複雑性理論の研究を続けました。博士号取得から4年後の2010年、彼は画期的な結果を証明しました。理論計算機科学における最も有名な問題である「難問の本質」の解決に向けた、小さな一歩ではありましたが、数十年ぶりの大きな前進でした。この成果はウィリアムズの名声を確固たるものにし、彼はその後も複雑性理論の様々なテーマについて数十本の論文を執筆しました。

P対PSPACEは、その問題の一つではありませんでした。ウィリアムズは大学で初めてこの問題に遭遇して以来、ずっと興味を抱いていました。時間と空間に関する他の視点からインスピレーションを得ようと、コンピュータサイエンスのカリキュラムに加えて論理学と哲学の授業も受講しましたが、結局何も得られませんでした。

「ずっと心の奥底で考えていたんです」とウィリアムズ氏は言った。「ただ、それについて何か面白いことを言うのが思いつかなかったんです」

昨年、彼はついに待ち望んでいた機会を見つけた。

スクイーズペブルズ

ウィリアムズ氏の新たな成果の物語は、計算におけるメモリに関する別の問いの進展から始まった。それは、極めて限られた空間でどのような問題を解けるか、という問いだ。2010年、複雑性理論の先駆者であるスティーブン・クック氏とその共同研究者たちは、「木評価問題」と呼ばれる課題を考案し、特定の閾値以下の空間予算を持つアルゴリズムではこの課題を解くことが不可能であることを証明した。しかし、そこには抜け穴があった。その証明は、ポール氏とその同僚たちが数十年前に立てたのと同じ常識的な仮定に基づいていた。アルゴリズムは、既に満杯になっている空間に新しいデータを保存できない、という仮定だ。

10年以上にわたり、複雑性理論家たちはこの抜け穴を塞ごうと試みてきました。そして2023年、クックの息子ジェームズとイアン・メルツという研究者が、この抜け穴を徹底的に解明し、誰も考えられなかったほど少ないメモリで木評価問題を解くアルゴリズムを考案しました。クックの証明では、データのビットはアルゴリズムのメモリ内で別々の場所を占める小石のようなものだと想定されていました。しかし、データを保存する方法はそれだけではないことが判明しました。「これらの小石は、互いに少し押しつぶせるものと考えることができます」とビーム氏は言います。

クックとメルツのアルゴリズムは多くの研究者の好奇心を掻き立てたが、木の評価問題以外に応用できるかどうかは明らかではなかった。「誰もそれが時間と空間そのものにとっていかに重要であるかに気づいていなかった」とウィグダーソンは語った。

ライアン・ウィリアムズは例外だった。2024年春、彼が担当していた授業の最終課題として、学生グループがクックとメルツの論文についてプレゼンテーションを行った。彼らの熱意に触発され、彼はさらに詳しく調べてみた。するとすぐに、あるアイデアが頭に浮かんだ。クックとメルツの手法は、実は空間使用量を削減するための汎用的なツールだと彼は気づいた。それを、ホップクロフト、ポール、ヴァリアントが設計したものと同様の、より優れた、時間と空間を結びつける新しい宇宙シミュレーションに活用してみてはどうだろうか？

この古典的な結果は、与えられた時間予算を持つあらゆるアルゴリズムを、わずかに少ない空間予算を持つ新しいアルゴリズムに変換する方法でした。ウィリアムズは、柔らかい小石を使ったシミュレーションによって、新しいアルゴリズムの空間使用量が大幅に削減されることに気付きました。これは、元のアルゴリズムの時間予算の平方根にほぼ相当します。この新しい空間効率の高いアルゴリズムは、実行速度も大幅に低下するため、シミュレーションを実用化できる可能性は低いでしょう。しかし、理論的な観点から見ると、それはまさに革命的なものでした。

研究者たちは50年間、ホップクロフト、ポール、ヴァリアントによる宇宙シミュレーションの改良は不可能だと考えていた。ウィリアムズのアイデアは、もし成功すれば、彼らの記録を破るだけでなく、それを打ち破ることになるだろう。

「考えてみたら、『そんなことはありえない』と思ったんです」とウィリアムズは言った。彼はそれを脇に置き、7月の運命の日まで再び取り上げることはなかった。議論の欠陥を見つけようとしたが、見つからなかったのだ。欠陥がないことに気づいた後、彼は数ヶ月かけて証明を書き直し、可能な限り明確にしようとした。

2月末、ウィリアムズはついに完成した論文をオンライン公開した。クックとメルツも皆と同じように驚いた。「他のことをする前に、長い散歩をしなければならなかったんです」とメルツは言った。

ヴァリアントは朝の通勤中に、ウィリアムズが数十年前の自身の結果を改善したことをこっそりと目にした。彼は長年、ハーバード大学で教鞭を執っている。ハーバード大学は、ウィリアムズのMITオフィスのすぐ近くにある。二人は以前にも面識があったが、結果が公表される数週間前の2月の雪の降る日にバスで偶然出会うまで、同じ地域に住んでいるとは知らなかった。ウィリアムズは驚くヴァリアントに証明を説明し、論文を送ると約束した。

「本当に、本当に感銘を受けました」とヴァリアント氏は語った。「50年間で最高の数学的結果が得られたなら、何か正しいことをしているに違いありません。」

PSPACE: 最後のフロンティア

ウィリアムズは新たなシミュレーションで、空間の計算能力に関する肯定的な結果を証明した。比較的小さな空間しか使わないアルゴリズムは、多少時間がかかる問題をすべて解けるというものだ。そして、わずか数行の計算を用いて、この結果を逆転させ、時間の計算能力に関する否定的な結果を証明した。少なくともいくつかの問題は、空間よりも多くの時間を使うことでしか解けないというものだ。この2番目の、より限定的な結果は、研究者の予想と一致している。奇妙なのは、ウィリアムズがどのようにしてそこに到達したかだ。まず、どんな問題を解くかに関わらず、すべてのアルゴリズムに当てはまる結果を証明したのだ。

「まだ信じられないんです」とウィリアムズさんは言った。「信じられないくらい素晴らしい話なんです」

定性的な言葉で表現すると、ウィリアムズの2番目の結果は、P対PSPACE問題に対する長年探し求められてきた解決策のように聞こえるかもしれない。違いはスケールの問題である。PとPSPACEは非常に広範な複雑性クラスであるのに対し、ウィリアムズの結果はより微細なレベルで作用する。彼は空間の力と時間の力の間に定量的なギャップを確立したが、PSPACEがPよりも大きいことを証明するには、研究者たちはそのギャップをはるかに大きく広げなければならないだろう。

これは非常に困難な課題で、歩道のひび割れをバールでこじ開けてグランドキャニオンの幅に広げるようなものだ。しかし、ウィリアムズのシミュレーション手順を改良し、重要なステップを何度も繰り返すことで、毎回少しずつスペースを節約することで、この目標に到達できるかもしれない。これは、バールの長さを繰り返し調整する方法のようなもので、十分な長さにすれば、何でもこじ開けることができる。この繰り返しの改良は現在のアルゴリズムでは機能しないが、研究者たちはそれが根本的な限界であるかどうかは分かっていない。

「これは究極のボトルネックになるかもしれないし、50年かかるボトルネックになるかもしれない」とヴァリアント氏は述べた。「あるいは、来週には誰かが解決できるかもしれない問題かもしれない」

もし来週に問題が解決したら、ウィリアムズは後悔するだろう。論文を書く前に、彼は何ヶ月もかけて結果を拡張しようと試みたが、失敗に終わった。しかし、たとえそのような拡張が不可能だとしても、ウィリアムズはさらなる宇宙探査が必ず興味深い何か、おそらく全く異なる問題の進展につながると確信している。

「証明したいことを正確に証明することは決してできない」と彼は言った。「でも、証明したものは、自分が望んでいたものよりずっと良いものであることがよくあるんです。」

編集者注: スコット・アーロンソンは、Quanta Magazine の諮問委員会のメンバーです。

オリジナルストーリーは 、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。