論文の概要: Exact Local Optimality Does Not Compose: The Complexity of Chronological Realization
- arxiv url: http://arxiv.org/abs/2609.19707v2
- Date: Tue, 22 Sep 2026 03:19:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-23 18:04:03.852878
- Title: Exact Local Optimality Does Not Compose: The Complexity of Chronological Realization
- Title（参考訳）: 厳密な局所最適性は成り立たず--時間的実現の複雑さ
- Abstract要約: 正規化実現は行確率遷移行列と終端効果を用いて宣言された根語応答を再現する。
独立局所現実化、独立クエリ効果を持つ静的共有キャリア、時系列共有現実化の3つの実化複雑性を比較した。
明示的に列挙された有理メニューでは、正確な共有実現性は$existsmathbbR$-completeであり、逆多項式とゼロ欠陥を区別する約束問題は$mathsfPromiseNP$-completeである。
- 参考スコア（独自算出の注目度）: 2.1248439796866228
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study a controlled, normalized multi-menu positive-realization problem. A normalized realization reproduces declared root--word responses using common row-stochastic transition matrices and a single terminal effect. We compare three realization complexities: independent local realizations, a static shared carrier with independent query effects, and chronological shared realizations. We construct response families for which the local and static optimum widths both equal $k$, isolating the additional cost imposed by chronological consistency. An explicit payload--delay family has exact width $k$ locally and statically but requires exact width $k(L+1)$ under shared chronological coupling, yielding an unbounded multiplicative separation. For explicitly listed rational menus, exact shared realizability is $\exists\mathbb{R}$-complete, while the promise problem of distinguishing zero defect from defect at least inverse-polynomial is $\mathsf{PromiseNP}$-complete. These finite-menu hardness results hold with five control letters and a single Boolean terminal effect. For regular response families generated by a geometric compiler, rank-tight realizability over the full infinite language is equivalent to realizability on a polynomial-size finite core. Consequently, exact rank-tight realizability for the compiled instances has an $\exists\mathbb{R}$ upper bound, complementing a strongly bounded-rational $\mathsf{PromiseNP}$-hardness result.
- Abstract（参考訳）: 制御された正規化されたマルチメニューの正準実現問題について検討する。
正規化実現は、共通の行確率遷移行列と単一の終端効果を用いて宣言された根語応答を再現する。
独立局所現実化、独立クエリ効果を持つ静的共有キャリア、時系列共有現実化の3つの実化複雑性を比較した。
我々は、局所最適幅と静的最適幅が等しい応答列を構築し、時間的一貫性によって課される追加コストを分離する。
明示的なペイロード-遅延族は、局所的および静的に正確な幅$k$を持つが、共有時間結合の下では正確な幅$k(L+1)$を必要とし、非有界乗法分離をもたらす。
明示的に列挙された有理メニューに対して、正確な共有実現性は$\exists\mathbb{R}$-completeであり、少なくとも逆多項式の欠陥からゼロ欠陥を区別する約束問題は$\mathsf{PromiseNP}$-completeである。
これらの有限次元硬さは、5つの制御文字と1つのブール終端効果を持つ。
幾何学的コンパイラによって生成される正則応答族に対して、フル無限言語上のランクタイト実現可能性は多項式サイズの有限コア上の実現可能性と同値である。
したがって、コンパイルされたインスタンスの正確なランクタイト実現性は$\exists\mathbb{R}$上界を持ち、強い有界有理数 $\mathsf{PromiseNP}$-hardness の結果を補完する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。