論文の概要: Towards a Doubly Efficient IP=PSPACE
- arxiv url: http://arxiv.org/abs/2606.21799v1
- Date: Fri, 19 Jun 2026 23:32:02 GMT
- ステータス: 情報取得中
- システム内更新日: 2026-06-23 14:47:48.444745
- Title: Towards a Doubly Efficient IP=PSPACE
- Title（参考訳）: 二重効率IP=PSPACEを目指して
- Authors: Liyan Chen, Matthew M. Hong, Yael Tauman Kalai, Zoe Xi,
- Abstract要約: PSPACEのすべての言語がチューリングマシンによって決定可能な時間$T(n)=nO(log n)$で決定可能であることを示す。
これは、そのような証明システムにおいて最もよく知られた体系を拡張している。
- 参考スコア（独自算出の注目度）: 7.597718642680558
- License:
- Abstract: We show that every language in PSPACE decidable by a Turing machine in time $T(n)=n^{O(\log n)}$ admits a doubly efficient interactive proof system: the prover runs in time polynomial in T(n), and the verifier runs in time polynomial in n. This extends the best previously known regime for such proof systems from $T(n)=n^{O(\sqrt{\log n / \log\log n})}$, established by Berger, Goyal, Hong, and Kalai (FOCS 2025), to $T(n)=n^{O(\log n)}$. Beyond improving the range of T, our protocol is substantially simpler than previous doubly efficient proofs for time-bounded PSPACE. Earlier constructions proceed indirectly: they first build batch interactive proofs and then invoke them as a black box to obtain doubly efficient protocols. In contrast, we give a direct construction. This not only simplifies the proof but also points to a more promising route for future improvements.
- Abstract（参考訳）: PSPACE のすべての言語がチューリングマシンで決定可能であることを示す: $T(n)=n^{O(\log n)}$ は2倍効率の対話的証明システムを持つ: 証明者は T(n) の時間多項式で実行し、検証者は n の時間多項式で実行される。
これは、ベルガー、ゴーヤル、ホン、カライ(FOCS 2025)によって確立された$T(n)=n^{O(\log n)}$から$T(n)=n^{O(\log n)}$まで、そのような証明系において最もよく知られた体系である。
Tの範囲を改良する以外に、我々のプロトコルは従来の2倍効率のPSPACEの証明よりも大幅にシンプルである。
初期の構成は間接的に進み、まずバッチインタラクティブな証明を構築し、それからブラックボックスとして呼び出し、二重効率なプロトコルを得る。
対照的に、直接的な構成を与えます。
これは、証明を単純化するだけでなく、将来の改善のためのより有望なルートも指している。
関連論文リスト
- Efficiently Representing Algorithms With Chain-of-Thought Transformers [45.60818649759173]
思考の連鎖変換器はチューリングマシンをシミュレートし、任意の計算を行う。
我々は,CoTエンファンカンが多対数オーバーヘッドのみのWord RAMアルゴリズムを$n$で効率的にシミュレートできることを示す。
論文 参考訳（メタデータ） (2026-06-18T01:49:29Z) - Efficiently Batching Unambiguous Interactive Proofs [8.993111413196559]
例えば、$Lotimes k$に属するステートメントのセット$k$-tuplesは、複雑さを伴うあいまいなインタラクティブな証明を持つ。 $ellcdotmathsfpolylog(k)$、$acdot ellcdotmathsfpolylog(k)$、ラウンドごとの通信である。
論文 参考訳（メタデータ） (2025-10-21T21:04:10Z) - Exponential Lindbladian fast forwarding and exponential amplification of certain Gibbs state properties [3.3728077347699497]
リンドブラディアン高速フォワード法とそのギブス状態特性推定への応用について検討する。
ファストフォワード(Fast-forwarding)とは、$t$よりもはるかに少ないクエリや回路深度を用いて、時間$t$のシステムをシミュレートする機能である。
論文 参考訳（メタデータ） (2025-09-11T14:57:53Z) - ProofWala: Multilingual Proof Data Synthesis and Theorem-Proving [53.67926215943612]
$rm P Small ROOFW Small ALA$は、ニューラル定理プローサと2つの確立された対話的証明アシスタント(ITP)間の相互作用を可能にする
私たちは、$rm P Small ROOFWsmall ALA$生成のCoqとLeanのデータの組み合わせでトレーニングされたモデルが、標準のprov-at-k$メトリック上で、Lean-onlyとCoq-onlyのモデルを上回っていることを示します。
論文 参考訳（メタデータ） (2025-02-07T05:35:46Z) - Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。
我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文 参考訳（メタデータ） (2023-06-02T17:49:35Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。
Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。
明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
論文 参考訳（メタデータ） (2020-10-15T04:42:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。