Exact Local Optimality Does Not Compose: The Complexity of Chronological Realization

技術要約：局所的な最適性は合成されない：時系列的実現の複雑性

問題提起
本論文は、単一の制御された遷移ダイナミクスを用いて、将来のレスポンス・メニューの集合を再現するために必要な最小の正規化確率状態次元 $C_{seq}$（時系列共有実現複雑性：Chronological Shared Realization Complexity (CRC)）を調査している。中心となる問いは、「局所的な予測および静的な因子分解の最適性が、共有された時系列的実現の最適性を意味するかどうか」である。

具体的には、著者は以下のランクタイト（rank-tight）領域に焦点を当てている：

1. 局所的複雑性 ($C_{loc}$): 各予測メニューのファミリーが、少数の潜在状態（$K$ で制限）を持つ独立した実現を許容する場合。
2. 静的複雑性 ($C_{stat}$): 各クエリに対して独立した効果を持つ、共有された正規化キャリアが存在し、それも $K$ で制限されている場合。
3. 時系列的複雑性 ($C_{seq}$): 単一の共有実現が存在し、かつそれが時系列的な一貫性（すなわち、クエリの効果が同一の原始的な遷移行列を介して単一の終端効果のプルバックであること）を維持できるかという問い。ここで、状態予算は $K$ である。

本論文は、「もし $C_{loc} = C_{stat} = K$ ならば、必ず $C_{seq} = K$ となるか？」と問うている。

手法
著者は、幾何学的実現理論、代数計算量、および組合せ論的構成を組み合わせた多角的なアプローチを採用している：

1. 幾何学的フレームワーク: 問題は、根（roots）が行確率ベクトルであり、制御（controls）が行確率行列であり、効果（effects）が列ベクトルである正規化確率的実現を用いて定式化される。著者は、**ランクタイトな時系列的閉包（rank-tight chronological closure）**の概念を用い、共有実現の存在を、遷移ダイナミクスから導出される一連のアフィン写像の下で不変な単体 $T$ の存在に関連付けている。
2. 明示的な構成（分離）: 「ペイロード–ディレイ（payload–delay）」ファミリーを構築することで、局所的／静的な境界と時系列的な境界との間の乗法的分離を示す。この構成は、局所的な実現ではデカップル（分離）できるが、時系列的な共有においては同時に強制されなければならない「共通のサフィックス（接尾辞）恒等式」を利用している。
3. 困難性還元:
   • $\exists\mathbb{R}$-完全性: 明示的にリストされた有理的な有限メニューに対し、ETR-INV（反転を伴う実数存在理論）問題からの還元を行う。著者は、「アイデンティティ校正（identity-calibrated）」インターフェースを用い、共有パラメータが加算と反転の代数制約を同時に満たすように強制する。
   • PromiseNP-完全性: 堅牢な決定問題（ゼロ欠陥と逆多項式欠陥の区別）において、有界出現3-SATからの還元を行う。これには、近似解をブール値に丸めるための全変動収縮を用いた「ブール分離（Boolean isolation）」メカニクトが用いられる。
4. 時系列コンパイラ（Chronology Compiler）: 汎用的なコンパイラを用いて、有界有理幾何学的ソースインスタンス（具体的には**中間単体（Intermediate Simplex）**問題）を、固定された5文字アルファベット上の制御されたレスポンス・ファミリーへと変換する。このコンパイラは、ランクタイトな予算を維持しつつ、「フェーズコード」と「ペイロード」構造を通じて時系列的一貫性を強制する。
5. 有限コア閉包（Finite-Core Closure）: 構成された正規ファミリーについて、無限の言語に対する厳密な実現可能性が、多項式サイズの有限コアに対する実現可能性と等価であることを証明する。これにより、無限の仕様から有限の仕様への困難性の転移を可能にしている。

主要な貢献と結果

1. 無限定な乗法的状態爆発（定理 2.2）:
   本論文は、局所的および静的な最適性が、時系列的な共有の下では合成されないことを確立している。特定のペイロード–ディレイ・ファミリーにおいて、$C_{loc} = C_{stat} = k$ であるとき、時系列共有複雑性は $C_{seq} = k(L + 1)$ となる（ここで $L$ はディレイ深度）。これにより、時系列的なプルバックの固有の状態で生じる乗法的なオーバーヘッドを特定し、時系列的一貫性が、局所的および静的な境界がタイトである場合でも、大幅な状態コストを強いる可能性があることを示している。

2. 厳密および堅牢な実現可能性の複雑性（定理 3.1）:

   • 厳密なケース: 明示的にリストされた有理的な有限メニューが、次元 $K$（ここで $C_{loc}=C_{stat}=K$）を持つ共有実現を許容するかどうかを判定することは、$\exists\mathbb{R}$-完全である。これは、問題が多項式系の実数解の存在を判定することと同等に困難であることを示している。
   • 堅牢なケース: ゼロ欠陥と逆多項式欠陥（$\epsilon$）を区別することは、PromiseNP-完全である。この困難性は、局的および静的な最適値が $K$ に固定されている場合でも成立する。

3. 正規ファミリーに対する困難性（定理 4.1）:
   汎用的な時系列コンパイラを用いることで、全パーサーによって生成される無限のリーガル・コントロール言語に対して、共有実現可能性を判定することが強力に有界有理 PromiseNP-困難であることを示す。

   • この還元は、中間単体問題（幾何学的被覆問題）を時系列的実現問題へと写像する。
   • コンパイラは、ランクタイトな予算 $K = kq$（ここで$q$ はパーサーセクター数）を保持する。
   • 定量的かつ堅牢な転移定理（定理 4.3）により、ソースの幾何学における逆多項式のギャップが、有限コアによって保証される形で、コンパイルされた実現における逆多項式の欠陥ギャップへと変換されることを確立している。

4. 有限コア閉包（定理 5.1）:
   コンパイルされた正規ファミリーについて、無限の言語全体に対する共有実現が存在するための必要十分条件は、多項式サイズの有限コアに対して存在することであると証明している。この結果は、これらの無限ファミリーに対する厳密な実現可能性問題を $\exists\mathbb{R}$ に位置づけ、困難性の結果に対する一致する上界を提供している。

意義と主張
本論文は、予測モデルにおいて時系列的一貫性を要求することによる固有の構造的および計算論的コストを孤立させていると主張している。

• 理論的ギャップ: 「局所的な予測妥当性」（低ランクの局所テスト）と「グローバルな動的実現可能性」（単一の共有更新システム）は、根本的に異なるものであることを示している。あるシステムは、局所的または静的には低次元に見えるかもしれないが、時系列的一貫性を維持するために、より大きな状態空間を必要とする場合がある。
• 計算論的不可能性: 局所的および静的な次元が最適である場合であっても、低次元の時系列的閉包が存在するかどうかを認識することは、計算論的に困難（厳密なケースでは $\exists\mathbb{R}$-完全、堅牢なケースでは PromiseNP-完全）であることを示している。
• 古典的ベースライン: 本フレームワークは、逐次的な量子プロセスにおける状態次元の境界に関する古典的なベースラインとして機能する（ここでは確率的ダイナミクスが完全正写像を一般化している）。著者は、同様の次元のギャップや代数的障害が量子共有実現においても存在する可能性があることを示唆しているが、これは未解決の課題として残されている。
• 限界: 著者は、自身の困難性構成が、増大する構造的次元（ペイロード次元 $D$ およびセクター数 $q$）に依存しており、固定パラメータ・レジーム（例：固定されたアルファベットサイズ、固定された根の数、または固定された共有次元）に対する困難性を主張するものではないと述べている。

要約すると、本論文は局所的最適性の合成に対する厳密な否定的な回答を提供している：厳密な局所的および静的な最適性は、時系列的な共有の下では必ずしも合成されない。また、そのような合成を検証することは計算論的に困難である。