休息中のハトが複雑性理論の中心にある理由

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

手の中の一羽は藪の中の二羽に勝る、と言われますが、コンピュータ科学者にとっては、穴の中の二羽の方がさらに価値があります。なぜなら、この共存する鳥たちが、「鳩小屋原理」と呼ばれる一見単純な数学定理の主人公だからです。この原理は、短い一文で簡単にまとめられます。「6羽の鳩が5つの鳩小屋に巣を作る場合、少なくとも2羽は1つの穴を共有しなければならない」。まさにその通りです。これが全てです。

「鳩の巣原理は、思わず笑みがこぼれるような定理です」と、コロンビア大学の理論計算機科学者、クリストス・パパディミトリウ氏は言う。「素晴らしい会話のネタになります。」

しかし、鳩の巣原理は鳥だけのものではありません。非常に単純に聞こえるにもかかわらず、理論計算機科学の中心的なプロジェクト、つまり異なる問題間の隠れたつながりをマッピングする研究者たちにとって、強力なツールとなっています。

鳩の巣原理は、項目がカテゴリに割り当てられ、項目の数がカテゴリの数を上回るあらゆる状況に適用されます。例えば、3万席の満員のサッカースタジアムでは、観客の中には必ず同じ4桁の暗証番号を持つ人がいます。ここで、鳩はサッカーファン、鳩の巣は0000から9999までの10,000通りの異なる暗証番号です。これは人数よりも少ないため、同じ数字を持つ人が必ずいることになります。

この証明は、その単純さだけでなく、何が欠けているかという点でも注目に値します。何かが存在することを証明する数学的手法の多くは「構成的」であり、つまり、その存在の発見方法も示してくれます。一方、鳩の巣原理に基づくような「非構成的」な証明には、この性質はありません。サッカースタジアムの例では、何人かの人が同じ暗証番号を持っているはずだと分かっていても、それが何なのかは分かりません。スタンドの全員に順番に尋ねていくこともできます。しかし、もっと簡単な方法はあるのでしょうか？

問題を最も効率的に解決する方法についてのこのような問いは、計算複雑性理論と呼ばれるコンピュータサイエンスの分野の中核を成しています。計算複雑性理論家は、特定の共通の性質に基づいて問題をクラスに分類することで、このような問いを研究します。時には、研究者がこれまでまとめて研究していなかった問題を統合する新しいクラスを定義するだけで、ブレークスルーへの第一歩を踏み出すことができるのです。

1990年代にパパディミトリウをはじめとする複雑性理論家たちが、鳩の巣原理やその他の非構成的証明によって存在しなければならない何かを見つけることを目標とする、新たな種類の問題を研究し始めたとき、まさにそれが起こりました。この研究は、暗号学からアルゴリズムゲーム理論に至るまで、コンピュータサイエンスの様々な分野において重要な進歩をもたらしました。

2020年1月までに、パパディミトリウは鳩の巣原理について30年間考え続けていました。そのため、頻繁に共同研究を行っている研究者との冗談めいた会話が、これまで考えたこともなかった原理の単純なひねりに繋がったとき、彼は驚きました。「もし鳩の数が穴の数より少なかったらどうなるだろうか？」と。その場合、鳩をどんなに並べても必ずどこかに空いた穴が残るはずです。これもまた自明の理のように思えます。しかし、鳩の巣原理を逆転させることで、何か興味深い数学的帰結が得られるのでしょうか？

この「空っぽの鳩小屋」原理は、単に名前を変えただけの元の原理のように聞こえるかもしれません。しかし、そうではありません。その微妙に異なる性質により、計算問題を分類するための新しく有益なツールとなっています。

空ピジョンホール原理を理解するために、銀行カードの例に戻りましょう。サッカースタジアムを3,000席のコンサートホールに置き換えてみましょう。3,000席というのは、4桁の暗証番号の可能な総数よりも少ない数です。空ピジョンホール原理によれば、いくつかの可能性のある暗証番号は全く提示されません。しかし、これらの見落とされた暗証番号を見つけたい場合、各人に暗証番号を尋ねる以外に良い方法はないようです。今のところ、空ピジョンホール原理は、より有名な対になるものと同じです。

違いは、解の検証の難しさにあります。例えば、サッカースタジアムで同じ暗証番号を持つ2人の人物を見つけたと誰かが言ったとします。この場合、元の鳩小屋のシナリオに対応して、その主張を検証する簡単な方法があります。問題の2人に確認するだけです。しかし、コンサートホールのケースでは、5926という暗証番号を持つ人はいないと主張する人がいたとします。この場合、観客全員に暗証番号を尋ねなければ検証は不可能です。そのため、空鳩小屋原理は複雑性理論家にとって非常に厄介なものになります。

パパディミトリウが空ピジョンホール原理について考え始めてから2か月後、彼は将来の大学院生との会話でその話題を持ち出した。彼はそれを鮮明に覚えている。というのも、それが新型コロナウイルス感染症によるロックダウン前に誰かと直接会話した最後の会話になったからだ。その後数か月間、家に閉じこもり、彼はこの問題が複雑性理論に与える影響について格闘した。最終的に、彼と彼の同僚は、空ピジョンホール原理によって解が保証される探索問題に関する論文を発表した。彼らは特に、ピジョンホールが豊富にある問題、つまりハトの数をはるかに上回る問題に興味を持っていた。複雑性理論における扱いにくい頭字語の伝統に従い、彼らはこの種の問題を「豊富な多項式空ピジョンホール原理」、つまりAPEPPと名付けた。

この授業の問題の一つは、コンピュータ科学者のパイオニアであるクロード・シャノンによる70年前の有名な証明に着想を得たものでした。シャノンは、ほとんどの計算問題は本質的に解くのが困難であることを証明しました。その際、空鳩の巣原理（シャノン自身はそう呼んでいませんでしたが）に基づく議論を用いました。しかし、コンピュータ科学者たちは何十年もの間、特定の問題が本当に難しいことを証明しようと試みてきましたが、失敗してきました。銀行カードの暗証番号が紛失したように、たとえ私たちが特定できなくても、難しい問題はどこかに存在しているはずです。

歴史的に、研究者たちは難しい問題を探すプロセスを、それ自体が数学的に解析可能な探索問題として捉えてこなかった。パパディミトリウのアプローチは、このプロセスを空鳩の巣原理に関連する他の探索問題とグループ化し、複雑性理論における近年の多くの研究に見られる自己言及的な特質を備えていた。つまり、計算困難性を証明することの難しさについて推論する新たな方法を提示したのだ。

「複雑性理論を使って複雑性理論の課題を分析しているのです」とコロンビア大学の研究者オリバー・コルテン氏は語った。

コルテンは、パンデミック直前にパパディミトリウが空鳩の巣原理について議論した、入学希望者だった。彼はパパディミトリウと共に研究するためにコロンビア大学に赴任し、大学院1年目に、難解な計算問題の探索がAPEPPにおける他のすべての問題と密接に関連していることを証明した。数学的な意味で言えば、この問題の進展は、単純な部分構造を持たないネットワークの探索など、コンピュータ科学者や数学者が長年研究してきた多くの他の問題の進展に自動的につながるだろう。

コルテンの論文はすぐに他の研究者の注目を集めた。「論文を見たときは本当に驚きました」と、オックスフォード大学の複雑性理論家、ラフル・サンタナムは語った。「信じられないほど刺激的です」。サンタナムをはじめとする研究者たちは、コルテンの画期的な発見を基に、計算困難さとランダム性の関連性について次々と新たな結果を証明してきた。

「これには驚くべき豊かさがあります」とパパディミトリウ氏は述べた。「複雑性における重要な問題の核心に迫るものです。」

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