Fugu-MT 論文翻訳(概要): $TIME[t] \subseteq SPACE[O(\sqrt{t})]$ via Tree Height Compression

論文の概要: $TIME[t] \subseteq SPACE[O(\sqrt{t})]$ via Tree Height Compression

arxiv url: http://arxiv.org/abs/2508.14831v1
Date: Wed, 20 Aug 2025 16:27:53 GMT
ステータス: 翻訳完了
システム内更新日: 2025-08-21 16:52:41.527008
Title: $TIME[t] \subseteq SPACE[O(\sqrt{t})]$ via Tree Height Compression
Title（参考訳）: TIME[t] \subseteq SPACE[O(\sqrt{t})]$ via Tree Height Compression
Authors: Logan Nye,
Abstract要約: 決定論的マルチテープチューリングマシンの平方根空間シミュレーションを実証する。鍵となるステップは、標準的な左深の簡潔な木を再認識するハイト圧縮理論である。アルゴリズム的には、一定の大きさのフィールド上の一定度のマップを持つ代数的リプレイエンジンは、レベル単位の一定サイズのトークンを保証する。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We prove a square-root space simulation for deterministic multitape Turing machines, showing $\TIME[t] \subseteq \SPACE[O(\sqrt{t})]$. The key step is a Height Compression Theorem that uniformly (and in logspace) reshapes the canonical left-deep succinct computation tree for a block-respecting run into a binary tree whose evaluation-stack depth along any DFS path is $O(\log T)$ for $T = \lceil t/b \rceil$, while preserving $O(b)$ work at leaves, $O(1)$ at internal nodes, and edges that are logspace-checkable; semantic correctness across merges is witnessed by an exact $O(b)$ window replay at the unique interface. The proof uses midpoint (balanced) recursion, a per-path potential that bounds simultaneously active interfaces by $O(\log T)$, and an indegree-capping replacement of multiway merges by balanced binary combiners. Algorithmically, an Algebraic Replay Engine with constant-degree maps over a constant-size field, together with pointerless DFS and index-free streaming, ensures constant-size per-level tokens and eliminates wide counters, yielding the additive tradeoff $S(b)=O(b + \log(t/b))$ for block sizes $b \ge b_0$ with $b_0 = \Theta(\log t)$, which at the canonical choice $b = \Theta(\sqrt{t})$ gives $O(\sqrt{t})$ space; the $b_0$ threshold rules out degenerate blocks where addressing scratch would dominate the window footprint. The construction is uniform, relativizes, and is robust to standard model choices. Consequences include branching-program upper bounds $2^{O(\sqrt{s})}$ for size-$s$ bounded-fan-in circuits, tightened quadratic-time lower bounds for $\SPACE[n]$-complete problems via the standard hierarchy argument, and $O(\sqrt{t})$-space certifying interpreters; under explicit locality assumptions, the framework extends to geometric $d$-dimensional models.
Abstract（参考訳）: 決定論的マルチテープチューリングマシンの平方根空間シミュレーションを証明し、$\TIME[t] \subseteq \SPACE[O(\sqrt{t})]$を示す。鍵となるステップは、ハイト圧縮理論(Height Compression Theorem)である。これは、(ログスペース内でも)標準左深の簡潔な計算ツリーを、ブロックリスペクションがDFSパスに沿って評価スタックの深さが$O(\log T)$ for $T = \lceil t/b \rceil$, while Preserving $O(b)$ work at leaves, $O(1)$ at internal node, and edge that are logspace-checkable; マージ間のセマンティックな正当性は、正確な$O(b)$ window replay at the unique interfaceによって確認される。この証明は、中間点(平衡)再帰(英語版)、$O(\log T)$で同時にアクティブなインターフェースをバウンドするパスごとのポテンシャル(英語版)、バランスの取れたバイナリコンバインダによるマルチウェイマージのインディグリーキャッピング置換(英語版)を用いる。アルゴリズム的には、定数サイズのフィールド上の定数度マップを持つ代数的リプレイエンジンと、ポインターレスDSSとインデックスなしストリーミングは、レベル単位のトークンを固定サイズで保証し、幅広いカウンタを排除し、追加のトレードオフを$S(b)=O(b + \log(t/b))$ for block sizes $b \ge b_0$ with $b_0 = \Theta(\log t)$, which at the canonical choice $b = \Theta(\sqrt{t})$ gives$O(\sqrt{t})$ space; $b_0$ルールは、ウィンドウをスクラッチするブロックを退避させる。構造は均一であり、相対論的であり、標準モデル選択に対して堅牢である。分岐プログラム上界 $2^{O(\sqrt{s})}$ for size-$$bounded-fan-in circuits, tightened quadratic-time lower bounds for $\SPACE[n]$-complete problem via the standard hierarchy argument, $O(\sqrt{t})$-space certification interpreters; 明示的な局所性仮定の下では、フレームワークは幾何$d$-dimensional modelまで拡張される。

関連論文リスト

Complexity of mixed Schatten norms of quantum maps [7.182449176083625]
我々は、空間間の線型写像の混合Schatten $|Phi|_qto p$ノルムの計算の複雑さについて研究する。 Phi$ が完全に正であれば、$q geq p$ のとき、p$ に対して $| Phi |_q が効率的に計算可能であることを示す。
論文参考訳（メタデータ） (2025-07-11T07:20:25Z)
Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文参考訳（メタデータ） (2022-10-15T09:22:22Z)
The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文参考訳（メタデータ） (2022-09-04T10:01:39Z)
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
論文参考訳（メタデータ） (2022-07-15T11:55:09Z)
Complexity and Avoidance [0.0]
適切な$f$と$p$に対して$q$と$g$があり、$mathrmLUA(q) leq_mathrms mathrmCOMPLEX(f)$と$q$と$g$の成長率があることを示す。シフト複雑性に関して、$$$q$が$rmLUA(q)$の任意のメンバに対して、$delta$-shift複素列を計算するためにどれだけ遅くなるかという明示的な境界が与えられる。
論文参考訳（メタデータ） (2022-04-24T14:36:38Z)
Coresets for Decision Trees of Signals [19.537354146654845]
仮にそのような行列に対して$(k,varepsilon)$-coresetを出力する最初のアルゴリズムを提供する。これは、決定木と -- 機械学習から -- 計算幾何学における分割木の間のリンクをフォージすることで実現している。
論文参考訳（メタデータ） (2021-10-07T05:49:55Z)
Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文参考訳（メタデータ） (2021-02-15T08:16:51Z)
On Computing Stable Extensions of Abstract Argumentation Frameworks [1.1251593386108185]
textitabstract argumentation framework (sc af) は有向グラフ $(A,R)$ であり、$A$ はtextitabstract arguments の集合であり、$Rsubseteq A times A$ は textit attack relation である。与えられた sc における全ての安定な拡張をリストアップするための、既知のバックトラックアルゴリズムの徹底的な形式的検証を示す。
論文参考訳（メタデータ） (2020-11-03T05:38:52Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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