論文の概要: Exact Local Optimality Does Not Compose: The Complexity of Chronological Realization

• arxiv url: http://arxiv.org/abs/2609.19707v1
• Date: Thu, 17 Sep 2026 05:01:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:54.113076
• Title: Exact Local Optimality Does Not Compose: The Complexity of Chronological Realization
• Title（参考訳）: 厳密な局所最適性は成り立たず--時間的実現の複雑さ
• Abstract要約: 時間共有実現複雑性(CRC)は、将来の応答メニューのコレクションを再現するために必要な最小の正規化状態次元$C_rm seq$である。 局所的な実現次元と独立な静的キャリア幅の両方が$K$に等しいランクタイト方式に着目する。 我々は,ランクタイト体制においても,時間的共有の下で正確な局所的および静的的最適性を構成する必要はないことを示した。
• 参考スコア（独自算出の注目度）: 2.1248439796866228
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The chronological shared realization complexity (CRC) is the smallest normalized stochastic state dimension $C_{\rm seq}$ needed to reproduce a collection of future-response menus using one shared family of controlled transition dynamics. We focus on the rank-tight regime in which both the local realization dimension and the independent-query static carrier width equal $K$, thereby isolating the additional dimensional and computational constraints imposed by chronological consistency. This framework also serves as the classical baseline for state-dimension bounds in sequential quantum processes, where stochastic dynamics generalize to completely positive maps. We establish three results in this regime. First, an explicit payload--delay family exhibits an unbounded multiplicative state blow-up: $C_{\rm loc}=C_{\rm stat}=k$ while $C_{\rm seq}=k(L+1)$, isolating the intrinsic state cost of shared temporal pullbacks. Second, for explicitly listed rational finite menus over a fixed five-letter alphabet with a single Boolean terminal effect, exact shared realizability is $\exists\mathbb{R}$-complete, and the zero-versus-inverse-polynomial defect promise problem is $\mathsf{PromiseNP}$-complete, with local and static optima fixed at $K$. Third, a total five-letter chronology compiler translates bounded-rational Intermediate Simplex instances into a polynomially specified regular geometric family over the same fixed alphabet, preserving exact local and static width $K$. The compiled family yields strong $\mathsf{PromiseNP}$-hardness for shared realization on strongly bounded-rational inputs, together with an $\exists\mathbb{R}$ upper bound certified by an exact polynomial-size finite core. Together, these results show that exact local and static optimality need not compose under chronological sharing, even in the rank-tight regime.
• Abstract（参考訳）: 時間的共有実現複雑性(CRC)は、制御遷移力学の共有族を用いて将来の応答メニューの集合を再現するために必要となる最小の正規化確率状態次元$C_{\rm seq}$である。 局所的な実現次元と独立な静的キャリア幅の両方が$K$と等しいランクタイトな状態に着目し、時間的整合性によって課される追加次元および計算的制約を分離する。 このフレームワークは、連続量子過程における状態次元境界の古典的なベースラインとしても機能し、確率力学は完全に正の写像に一般化される。 私たちはこの体制で3つの結果を確立します。 C_{\rm loc}=C_{\rm stat}=k$ while $C_{\rm seq}=k(L+1)$。 第二に、ブール終端効果が1つある固定された5文字アルファベット上の有理有限メニューを明示的に列挙すると、正確な共有実現性は$\exists\mathbb{R}$-complete、ゼロ対逆ポリーノミアル欠陥保証問題は$\mathsf{PromiseNP}$-complete、局所および静的オプティマは$K$で固定される。 第3に、合計5文字のクロノロジーコンパイラは、有界有理中間体Simplexインスタンスを、同じ固定アルファベット上の多項式的に指定された正則な幾何学ファミリに変換し、正確な局所的および静的な幅を$K$で保存する。 コンパイルされた族は、強い有界有理数入力に対する共有実現のために強い$\mathsf{PromiseNP}$-hardnessと、正確な多項式サイズの有限コアによって証明された$\exists\mathbb{R}$上界を得る。 これらの結果は、ランクタイト体制においても、時間的共有の下で正確な局所的および静的な最適性を構成する必要はないことを示している。

関連論文リスト

• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• Incremental Sheaf Cohomology on Cellular Complexes: O(1)-in-n Lazy Edit Processing under Bounded Local Geometry [0.0]
  最初のせん断コホモロジーの漸進的維持のためのアルゴリズム的枠組み:H1(X; MathcalF)$ 有限次元の細胞シーブを備えた動的に進化する1次元細胞複合体について。
  論文  参考訳（メタデータ） (2026-06-02T21:26:02Z)
• Structural Conditions for Native CCZ Magic-State Fountains in qLDPC Codes [5.685589351789461]
  量子低密度パリティチェック(qLDPC)符号は、有界重みチェックを持つ定格線形距離ファミリーを約束する。 明示的なエンフィクビットqLDPC族は、定数速度、線形距離、有界安定度重み、および多くの非クリフォード資源状態を一定の深さで準備する固有なアンフィクティック状態の噴水を同時に持つことが知られている。
  論文  参考訳（メタデータ） (2026-01-30T02:59:06Z)
• Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
  この研究は、パーソナライズされたPageRank計算を高速化するために、ネストした進化したセットプロセスに基づく新しいフレームワークを提案する。 このような局所化手法の時間複雑性は、PPRベクトルの$epsilon$-approximationを得るために$mintildemathcalO(R2/epsilon2), tildemathcalO(m)$によって上界となることを示す。
  論文  参考訳（メタデータ） (2025-10-09T09:47:40Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。