技術要約：3-VASSの到達可能性問題はEXPSPACEに属する

問題設定

本論文は、3次元ベクトル加算システム（3-VASS）の到達可能性問題を扱っている。VASSとは、非負整数を保持する固定数のカウンタ（次元）を備えた有限状態オートマトンである。到達可能性問題とは、あるターゲット構成（状態とカウンタの値）が、有効な遷移の列によってソース構成から到達可能であるかどうかを問うものである。

一般的なVASSの到達可能性問題（次元が入力の一部となる場合）は、2021年にACKERMANN完全であることが証明されているが、固定された次元 $d > 2$ における正確な複雑性は依然として中心的な未解決問題である。特に3-VASSについては以下の通りである：

• 下界： 2次元の場合から継承されたPSPACE困難であることが知られている。
• 従来の計算量の上界： 本研究までは、Czerwińskiら（ICALP 2025）によって確立された2-EXPSPACE（二重指数空間）が最良の上界であった。それ以前のアルゴリズムは非初等（non-elementary）であった。

本論文の目的は、3-VASSの到達可能性問題がEXPSPACE（単一指数空間）に属することを証明することで、PSPACEの下界と2-EXPSPACEの上界の間のギャップを埋めることにある。

手法および証明戦略

証明の核心は、3-VASSにおける2つの構成間の最短実行の二重指数的な長さの境界を確立することにある。もし最短実行の長さが $N^{2^{poly(k)}}$ （ここで $N$ は入力サイズ、$k$ は強連結成分の数）で抑えられるならば、その長さのパスを非決定的に推測することで、到達可能性をEXPSPACEで決定できる。

著者らは、階層的還元戦略と**関心の分離（separation-of-concerns）**という証明技法を採用し、3-VASSのインスタンスを一連のサブクラスへと精緻化している。このアプローチにより、以前の著作で見られた「入れ子状」の帰納法（これが三重指数的な境界を招いた）を回避している。

1. VASSの階層的分類

論文では、増加する一般性に基づいて、3-VASSのサブクラスの階層を以下のように定義している：
$$\text{DiagVASS}_3 \subsetneq \text{Semi-diagVASS}_3 \subsetneq \text{PumpVASS}_3 \subsetneq \text{Semi-pumpVASS}_3 \subsetneq \text{SeqVASS}_3$$

• DiagVASS: 前方および後方の両方に「対角線的」なサイクル（すべてのカウンタを正方向にポンプできるサイクル）が存在するインスタンス。
• PumpVASS: 前方および後方の両方に「ポンプ可能な」サイクル（少なくとも一つのカウンタを正方向にポンプできるサイクル）が存在するインスタンス。
• SeqVASS: 一般的な逐次的（sequential）VASS。実行がブリッジによって接続された強連結成分（SCC）の列を横断する。

証明は、最も制約の強いクラス（DiagVASS）に対して長さの境界を確立することから始まり、その後、**長さ制御された自己還元（length-controlled self-reductions）**を用いて、これらの境界をより一般的なクラスへと転送する手順で進められる。

2. 主要な技術的構成要素

A. 到達可能集合の効率的な表現（幾何学的な2次元VASS）

重要なツールは、すべての実行が2つの平行な2D平面の間に留まる幾何学的な2次元VASSの解析である。著者らは、Czerwińskiらによる結果を拡張し、たとえ「ハイブリッド集合」（ベースとなるベクトルと制限された周期集合）から始まる場合であっても、そのようなシステムの到達可能集合が、多項式サイズの記述を持つハイブリッド集合の有限和として表現できることを示した。これにより、表現サイズの指数的な増大を招くことなく、到達可能集合を効率的に操作することが可能になる。

B. 非ワイドな対角線インスタンスの処理

DiagVASSについて、著者らは「ワイド（wide）」なインスタンスと「非ワイド（non-wide）」なインスタンスを区別している。

• Wide: システムの逐次的錐（sequential cone）がすべての正のベクトルを含む。これらは既知の結果への還元によって処理される。
• Non-Wide: 著者らは、非ワイドな対角線インスタンスにおいて、実行の接頭辞（prefix）と接尾辞（suffix）の逐次的錐が超平面によって分離されることを証明している。この幾何学的な分離は、中間成分におけるカウンタの値が一対の平行な2D平面内に制約されることを意味する。その結果、この問題は一連の幾何学的な2次元VASSインスタンスへと変換可能となり、上述の効率的な表現技法を適用して二重指数の長さの境界を導出することができる。

C. 長さ制御された自己還元

PumpVASSおよびSeqVASSからDiagVASSへ移行するために、論文では長さ制御された自己還元を導入している。

• 結合的な対角性の抽出: ポンプ可能なインスタンスに対して、著者らは「結合的に対角的な」接頭辞（すべてのカウンタを集合的にポンプするサイクルの列）を抽出できることを示している。
• 還元: この接頭辞を用いて、より少ないコンポーネント（またはより単純な構造）を持ち、かつ対角的である新しいVASSインスタンスを構成する。この新しいインスタンスのサイズは、対象となるクラスの長さ関数によって制御される。
• 入れ子の回避: 長さの境界関数を（例：$h_k(h_{k-1}(\dots))$ のように）入れ子にする従来のアプローチとは異なり、この手法は、再帰の右辺に長さの境界が一度だけ現れることを保証する。この構造的な変更こそが、複雑さを2-EXPSPACEからEXPSPACEへと減少させた要因である。

主要な貢献と結果

1. メイン定理: 3-VASSの到達可能性問題はEXPSPACEに属する。

   • これは、入力の単項符号化およびバイナリ符号化の両方に対して成立する。
   • 証明は、任意の $k$ コンポーネントの3-VASSにおいて、最短実行の長さが $size(V, s, t)^{2^{poly(k)}}$ で抑えられることを示すことに依拠している。

2. 精緻化された複雑性の景観: 論文は3-VASSのサブクラスの複雑性に関する詳細な分析を提供している：

   • DiagVASS3: EXPSPACEに属することを証明（従来の2-EXPSPACEの上界を改善）。
   • PumpVASS3: 二重指数的に短い実行を持つことを証明。
   • SeqVASS3: PumpVASSへの自己還元を通じて、二重指数的に短い実行を持つことを証明。

3. 方法論的な進展: 論文は、階層的なポンプ可能性分析と関心の分離戦略を導入している。問題を幾何学的な2次元の部分問題へと分解し、コンポーネントの階層を尊重する自己還元を用いることで、従来の帰納的証明に内在していた三重指数の増大を排除している。

意義と主張

本論文は、理論計算機科学における長年の課題であった3-VASS到達可能性問題の理解を大きく進展させたと主張している。

• 境界の絞り込み: この結果は、3-VASSの複雑性のギャップを、二重指数的な上界から単一指数的な上界へと狭めている。下界は依然としてPSPACEであるが、著者らは、一般的な3-VASSからポンプ可能な3-VASSへの還元は多項式空間では行えない可能性が高いことから、3-VASSは実際にEXPSPACE困難である可能性があると指摘している。
• 将来の研究への基礎: 論文は、その正確な複雑性（PSPACEかEXPSPACEか）を決定することは依然として未解決であることを明記している。また、二重指数的な最短実行を持つ3-VASSの例を示すことが、決定的なEXPSPACE困難性の証明には必要であるが、それは現在未知であるとも述べている。
• 高次元への影響: 著者らは、最短実行を境界付ける彼らの視点が、$d \ge 4$ 次元のVASSを分析する上で有益である可能性があることを示唆している。これらの次元における現在の計算量の上界は、初等的（elementary）な範囲から遠く離れている。

要約すると、本論文は、幾何学的な分離議論、効率的な到達可能集合の表現、および複雑さの増大を回避する精緻な自己還元フレームワークを組み合わせることで、3-VASSの到達可能性問題が指数空間で解けることを厳密に証明している。