5 歳児がコンピューター サイエンスの最前線の疑問を理解できることはあまりありませんが、それが起こる可能性はあります。 たとえば、アリスという名前の幼稚園児はリンゴを XNUMX つ持っていますが、オレンジの方が好きだとします。 幸いなことに、彼女のクラスメートは、為替レートを厳格に適用した健全な果物取引システムを開発しました。たとえば、リンゴをあきらめれば、バナナを手に入れることができます。 アリスは、バナナやマスクメロンを拾ったり降ろしたりする一連の取引を実行して、お気に入りの果物を手に入れることができるでしょうか?

とてもシンプルに聞こえます。 「小学校に行って子供たちに教えてください」と彼は言いました。 クリストフ・ハーセ, オックスフォード大学のコンピューター科学者。 「人々は『それは簡単だろう』と思うでしょう。」

しかし、アリスのジレンマの根底にある数学的問題 (ベクトル加算システムの到達可能性問題と呼ばれる) は、驚くほど微妙です。 簡単に解決できるケースもありますが、コンピューター科学者は、この問題を包括的に理解するために半世紀近くにわたって苦労しました。 現在、過去数年間にわたる一連の画期的な進歩により、彼らはこの問題がどれほど複雑になるかを正確に証明しました。

この子供のような問題は、ばかばかしく、ほとんど漫画のように複雑であることが判明しました。あまりにも複雑なので、実際には他のすべての問題が 有名な難しい計算問題 まあ、子供の遊びのように見えます。 この問題を解くのに必要な労力を数値化してみると、すぐに桁数を数えるだけでも聞いたことのない数字にたどり着くほど大きな数字に直面することになるでしょう。 このような数字はしばしば宇宙の規模との比較を招きますが、そのたとえさえも不十分です。 「それは正当な評価にはならないだろう」と彼は言った ゲオルク・ツェチェ、ドイツのカイザースラウテルンにあるマックス・プランク・ソフトウェア・システム研究所のコンピュータ科学者。 「宇宙はとても小さいです。」

届く範囲で？

本質を突き詰めると、到達可能性の問題は、順序付けられた数値のリストであるベクトルと呼ばれる数学的オブジェクトに関するものです。 これらのリストのエントリはコンポーネントと呼ばれ、ベクトル内のコンポーネントの数はその次元と呼ばれます。 たとえば、アリスの果物の在庫は XNUMX 次元ベクトル (a, b, c, d), その構成要素は、彼女が常に持っているリンゴ、バナナ、マスクメロン、オレンジの数を表します。

ベクトル加算システム (VAS) は、システム内の状態間の可能な遷移を表すベクトルの集合です。 アリスの場合、遷移ベクトル (-1, -1, 1, 0) は、リンゴとバナナとマスクメロンの交換を表します。 VAS 到達可能性の問題では、特定の初期状態から特定のターゲット状態に移行できる許可された遷移の組み合わせがあるかどうか、または数学的に言えば、開始ベクトルをターゲット ベクトルに変換する遷移ベクトルの合計があるかどうかが問われます。 問題が XNUMX つだけあります。システムの状態を記述するベクトルのどの成分も XNUMX を下回ることはありません。

「これは現実のモデルにとって非常に自然な制限です」と彼は言いました。 ヴォイチェフ・チェルヴィンスキー、ワルシャワ大学のコンピューター科学者。 「負の数のリンゴを持つことはできません。」

一部のシステムでは、ターゲット ベクトルが到達可能かどうかを簡単に判断できます。 しかし、常にそうとは限りません。 コンピュータ科学者は、到達可能性を判断することがどれほど難しいか明らかではない、単純に見えるベクトル加算システムに最も興味を持っています。 それらのケースを研究するために、研究者は、特定のシステムのサイズを定量化する数値を定義することから始めます。 この数値は次のように表されます。 n、次元数、遷移数、その他の要素が含まれます。 次に、到達可能性の問題の難易度はどのくらいの速さで増加する可能性があるかを尋ねます。 n 大きくなります。

この質問に答えるために、研究者は XNUMX つの補完的なアプローチを使用します。 まず、彼らは、到達可能性の決定に最小限の努力が必要な、特に扱いにくいベクトル加算システムの例を検索します。 これらの最小レベルは、問題の複雑さの「下限」と呼ばれます。彼らは研究者にこう言います。 n 少なくともこれくらい難しいです。」

第二に、研究者は「上限」、つまり、最も悪魔的なシステムであっても、到達可能性がどの程度難しくなるかについての制限を確立しようとしています。 これらは次のように述べています。 n せいぜいこれくらい難しいです。」 最もトリッキーなシステムにおける到達可能性がどの程度難しいかを正確に判断するために、研究者は、下限を上げ、上限が満たされるまで押し下げようとします。

悪夢のようなもの

ベクトル加算システムには長い歴史があります。 1960 年代以来、コンピューター科学者は、計算を多くの小さな部分に分割し、それらの部分を同時に処理するプログラムのモデル化にこれらを使用してきました。 この種の「同時コンピューティング」は現在どこにでも普及していますが、研究者はまだその数学的基礎を完全には理解していません。

1976 年に、コンピューター科学者は、 リチャード・リプトン VAS 到達可能性問題の複雑さを理解するための第一歩を踏み出しました。 彼は、ある状態から別の状態に到達可能かどうかを判断する最速の方法は、それらの間の一連の遷移を計画することである、システムを構築するための手順を開発しました。 これにより、慎重に選択した XNUMX つの状態間の最短経路の長さを、到達可能性の問題の難易度の尺度として使用できるようになりました。

そのときリプトン 証明 彼はある程度の規模のシステムを構築することができた n この場合、2 つの状態間の最短経路には $latex 2^{2^n}$ 個以上の遷移が含まれます。 これは、彼のシステムの到達可能性を決定するために必要な労力に対応する二重指数関数的な下限を意味します。 これは驚くべき発見でした。5 倍の指数関数的成長はコンピューター科学者にとって悪夢のようなものです。 実際、研究者は、比較すると見劣りする通常の指数関数的増加ですら躊躇することがよくあります。$latex {32^2}= 2$ ですが、$latex 5^{4^XNUMX}$ は XNUMX 億を超えています。

ほとんどの研究者は、リプトンが可能な限り最も複雑なベクター加算システムを作り上げた、つまり下限を可能な限り高くしたと考えていました。 この場合、不足している唯一のものは、それに伴う上限です。つまり、到達可能性の決定がさらに難しいシステムは存在し得ないという証拠です。 しかし、それを証明する方法を誰も知りませんでした。 コンピュータ科学者のエルンスト・マイヤー氏が最も近い存在でした。 証明 1981 年に、原理的には、どのようなベクトル加算システムでも到達可能性を判断することが常に可能であると発表されました。 しかし、彼の証明は、問題がどれほど難しいかについて定量的な上限を設定しませんでした。 床はありましたが、天井は見えませんでした。

「確かに、断続的にそれについて考えました」とリプトンは語った。 「しかし、しばらくして私は諦めました。私の知る限り、40年間ほどの間、誰も進歩した人はいませんでした。」

2015 年、コンピューター科学者たちは、 ジェローム・ルルー & シルヴァン・シュミッツ ついに確立された 定量的な上限 このレベルは非常に高いため、研究者らはこれがリプトンの下限を満たすために押し下げられる可能性がある最初のステップにすぎないと考えた。

しかし、それは起こりませんでした。 2019年、研究者らはリプトンの限界よりもはるかに高い下限を発見し、数十年にわたる常識を覆した。 VAS の到達可能性の問題は、誰もが予想していたよりもはるかに複雑でした。

権力の塔

2019 年の衝撃的な結果は失敗から生まれました。 2018年、チェルウィンスキーはルルーと フィリップ・マゾヴィツキ、現在ワルシャワ大学のコンピューター科学者である彼は、関連する問題の進歩に貢献しただろう。 その後の議論で、研究者らは、超複雑ベクトル加算システムを構築する有望な新しい方法を思いつきました。これは、進歩が長らく停滞していたVAS到達可能性問題に新たな下限を示唆する可能性があります。

「私の頭の中ではすべてが VAS の到達可能性と結びついていました」とチェルウィンスキーは思い返します。 授業の負担が軽い学期の間、彼はルルー、マゾヴィツキ、そして他の二人の研究者とともに、その問題だけに集中することに決めた。 スワウォミール・ラソタ ワルシャワ大学の ランコ・ラジッチ ワーウィック大学の

数か月後、彼らの努力は報われました。 チェルウィンスキーと彼の仲間たち 実証 彼らは、悪夢のようなXNUMX倍の指数関数的成長さえも大人しく見せるテトレーションと呼ばれる数学的演算によって、XNUMXつの状態間の最短経路がシステムのサイズに関連付けられるベクトル加算システムを構築できると考えた。

テトレーションは、加算から始まる数学で最もよく知られた演算を接続するパターンを直接拡張したものです。 一緒に追加する n 数値のコピーであり、結果はその数値を乗算することと同じになります。 n。 一緒に掛け合わせると n 数値のコピー。これは、べき乗、または数値を累乗することに相当します。 n番目の力。 多くの場合、上向きの矢印のペアで表されるテトレーションは、このシーケンスの次のステップです。次の手順で数値をテトレーションします。 n 累乗することを意味します n 力の塔を生成するのにかかる時間 n 高い話。

テトレーションがどれほど早く手に負えなくなるかを理解するのは困難です。$latex 2 uparrowuparrow 3$ または $latex 2^{2^2}$ は 16、$latex 2 uparrowuparrow 4$ は 65,000 をわずかに超えます。 $latex 2 uparrowuparrow 5$ は、20,000 桁近い数字です。 $latex 2 uparrowuparrow 6$ のすべての桁を書き出すことは物理的に不可能です。これは、このような小さな宇宙に住む義務です。

チェルヴィンスキーと彼の同僚は、画期的な結果として、次のサイズのベクトル加算システムが存在することを証明しました。 n ここで、到達可能性を判断する最良の方法は、$latex 2 uparrowuparrow n$ 遷移を超えるパスを計画することです。これは、リプトンの限界を矮小化する新しい下限を意味します。 しかし、テトレーションと同様に頭がくらくらするが、それでも問題の複雑さについての最終決定には至らなかった。

XNUMX億千億、そしてその先へ 

VAS 到達可能性の複雑さに関する衝撃的な新しい下限が発表されてからわずか数か月後、Leroux と Schmitz は次のように述べています。 プッシュダウン 彼らがXNUMX年前に設定した上限でしたが、テトレーションまでは到達しませんでした。 その代わりに、彼らは、到達可能性の問題の複雑さが、アッカーマン関数と呼ばれる数学的な怪物よりも速く成長することはできないことを証明しました。

その機能を理解するには、テトレーションの定義に使用されるパターンをその厳しい結論にまで遡って考えてみましょう。 シーケンスの次の操作はペンテーションと呼ばれ、テトレーションの繰り返しを表します。 その後に、ペンテーションを繰り返すためのさらに別の操作 (ヘクセーション) が続きます。

$latex A(n)$ で示されるアッカーマン関数は、数直線上の各ストップでこの演算のはしごを 1 ステップ上に移動すると得られるものです: $latex A(1) = 1 + 2$, $latex A (2) = 2 × 3$、$latex A(3) = 3^4$、$latex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$、など。 $latex A(1)$ の桁数自体は、1 京 153 千億にほぼ等しい巨大な数です。これは、5 の後に XNUMX 個のゼロが続く、風変わりでめったに必要とされない名前です。 「XNUMXのアッカーマンのことは心配しないでください」とアドバイス ハビエル・エスパルサ、ミュンヘン工科大学のコンピューター科学者。

Leroux と Schmitz の結果では、下限と上限の間に大きなギャップが残されました。VAS 到達可能性問題の正確な複雑さは、範囲の両端またはその間のどこかにある可能性があります。 チェルウィンスキーにはその差を放置するつもりはなかった。 「これが私たちの人生で最大のことであることは明らかだったので、私たちはこれに取り組み続けました」と彼は言いました。

最後の突破口は2021年に訪れ、チェルヴィンスキーはウカシュ・オルリコフスキという名前の学部XNUMX年生にアドバイスをしていた。 彼は Orlikowski にこの問題の簡単な変形を割り当てて、スピードを上げさせました。Orlikowski の研究は、XNUMX 人が一般的な到達可能性の問題にも適用できる新しい手法を開発するのに役立ちました。 それによって彼らはできるようになった 下限を上げる 実質的には、ルルーとシュミッツのアッカーマンの上限までずっとです。 独立して働き、ルルーは 同等の結果 ほぼ同時に。

研究者たちはついに、到達可能性問題の真の複雑さを突き止めました。 Czerwiński、Orlikowski、Leroux の下限は、XNUMX つの状態間の最短経路がアッカーマン関数に比例して増大する、段階的に大きくなるベクトル加算システムのシーケンスが存在することを示しました。 ルルーとシュミッツの上限は、到達可能性の問題がこれ以上複雑になることはないことを示しました。問題を解決するための確実な実践手順を望んでいる人にとっては、ほとんど慰めになりません。 これは、単純に見える計算問題がいかに微妙であるかを示す印象的な例です。

未完成

研究者らは、VAS 到達可能性問題の正確な複雑性を判断した後、この問題の多くのバリエーションが未解決のまま研究を続けてきました。 たとえば、アッカーマンの上限と下限は、異なる増加方法を区別しません。 n, たとえば、ベクトルの次元を増やしたり、許可される遷移の数を増やしたりします。

最近、チェルウィンスキーと彼の同僚は、 進歩した 次元が固定されたベクトル加算システムのバリアントで複雑さがどのくらい早く増加するかを研究することで、これらの異なる効果を解明します。 しかし、やるべきことはまだたくさんあります。ベクトル加算システムが容易に視覚化できる XNUMX 次元でも、到達可能性の問題の正確な複雑さは不明のままです。

「ある意味、これは我々にとって恥ずかしいことだ」とマゾビツキ氏は語った。

研究者らは、比較的単純なケースをより深く理解することで、ベクトル加算システムよりも複雑な他の計算モデルを研究するための新しいツールの開発に役立つことを期待しています。 現時点では、これらのより精巧なモデルについてはほとんど何もわかっていません。

「私はこれを、計算可能性を理解するための非常に基本的な探求の一部であると考えています」とツェッチェ氏は述べた。

クアンタ では、視聴者により良いサービスを提供するために一連のアンケートを実施しています。 私たちのものを取ってください コンピュータサイエンス読者アンケート そしてあなたは無料で当選するためにエントリーされます クアンタ 商品。