論文の概要: MIPco=coRE

• arxiv url: http://arxiv.org/abs/2510.07162v1
• Date: Wed, 08 Oct 2025 15:59:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.606991
• Title: MIPco=coRE
• Title（参考訳）: MIPCO=coRE
• Authors: Junqiao Lin,
• Abstract要約: 2020年、Ji, Natarajan, Vidick, Wright, Yuen らは、複数のプロバーサを共有する絡み合いと相互作用する古典的検証器によって決定できる言語クラス MIP* が RE に等しいことを示した。 MIPco は MIP* に類似して定義される複雑性クラスであり、交換作用素モデルを共有するプローバーはクラス coRE に等しいことを示す。 このことは、プロバーが2つの異なる絡み合いモデルを与えると、インタラクティブな証明システムに対して2つの全く異なる計算能力が得られることを示している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen showed that MIP*, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP* except with provers sharing the commuting operator model of entanglement, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP*=RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP* =RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084]. We introduce a new equivalence condition for RE/coRE-complete problems, which we call the weakly compressible condition. We show that both MIP* and MIPco satisfy this condition through the compression theorem, and thereby establish that the uncomputability for MIP* and MIPco can be proved under a unified framework (despite these two complexity classes being different). Notably, this approach also gives an alternative proof of the MIP*=RE theorem, which does not rely on the preservation of the entanglement bound. In addition to non-local games, this new condition could also potentially be applicable to other decision problems.
• Abstract（参考訳）: 2020年、Ji, Natarajan, Vidick, Wright, Yuen による画期的な結果は、テンソル積モデルにおける複数の計算的非有界なプロバーサ共有絡み合わせと相互作用する古典的検証器によって決定できる言語クラス MIP* が RE に等しいことを示した。 MIPco は MIP* に類似して定義される複雑性クラスであり、交換作用素モデルを共有するプローバーはクラス coRE に等しいことを示す。 このことは、プロバーが2つの異なる絡み合いモデルを与えると、インタラクティブな証明システムに対して2つの全く異なる計算能力が得られることを示している。 我々の証明は、MIP*=REの証明で用いられる圧縮定理に基づいており、また、MIP*=REにおける同じ圧縮手順が、交換演算子設定において同じ望ましい性質を持つことを示すために、戦略的に埋め込み可能な戦略フレームワークを用いている。 また、Mousavi et al (STOC 2022] の同期フレームワークと、de la Salle (ArXiv:2204.07084) が導入した改良されたパウリ基底試験を組み込むことにより、非局所ゲームに対する圧縮定理のより簡潔な証明を与える。 我々はRE/coRE完全問題に対する新しい等価条件を導入し、弱い圧縮性条件と呼ぶ。 MIP* と MIPco はともに圧縮定理によりこの条件を満たすことを示し、したがって MIP* と MIPco の計算不可能性を統一的な枠組みの下で証明できることを示す。 特に、このアプローチは、絡み合い境界の保存に依存しないMIP*=RE定理の別の証明を与える。 非ローカルゲームに加えて、この新しい条件は他の決定問題にも適用できる可能性がある。

関連論文リスト

• Succinct Perfect Zero-knowledge for MIP* [1.839056773828158]
  本稿では,RE の不正な検証に対する完全ゼロ知識 MIP* プロトコルが存在することを示す。 質問の削減は、正当性検証に対する元のプロトコルの完全なゼロ知識特性を保っていることを示す。 第2に、MIP*の量子情報特徴を提供する制約制約バイナリ制約系(BCS)非局所ゲームは、同期制約変数のBCSゲームに変換され、圧縮の完全性を維持することができることを示す。
  論文  参考訳（メタデータ） (2025-03-06T15:05:22Z)
• On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
  CoT推論による現代言語モデル(LM)の性能向上 LMは弦上の分布の族を確率的チューリングマシンと同一に表現できることを示す。
  論文  参考訳（メタデータ） (2024-06-20T10:59:02Z)
• Two prover perfect zero knowledge for MIP* [0.0]
  MIP*のすべての言語は、PZK-MIP*プロトコルを2つのプロプライエタリに持つことを示す。 また、通信演算子BCSプロトコルを持つ全ての言語は、2つの証明子PZK通信演算子プロトコルを持つことを示した。
  論文  参考訳（メタデータ） (2024-04-01T05:07:22Z)
• Efficient Computation of Counterfactual Bounds [44.4263314637532]
  我々は,構造因果モデルのサブクラスにおけるクレダルネットのアルゴリズムを用いて,正確な反ファクト境界を計算する。 近似の精度を信頼性のある間隔で評価する。
  論文  参考訳（メタデータ） (2023-07-17T07:59:47Z)
• Tracially embeddable strategies: Lifting MIP* tricks to MIPco [0.0]
  通勤運転者モデルにおける二者相関は, 戦略的に組込み可能な戦略を用いて近似できることを示す。 また、ゴワーズ・ハタミ定理の状態依存ノルム多様体を有限フォンノイマン代数に拡張する。
  論文  参考訳（メタデータ） (2023-04-04T16:41:30Z)
• A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games [104.3339905200105]
  この研究は、ミラー降下と非ユークリッド近位勾配アルゴリズムにインスパイアされた、磁気ミラー降下と呼ばれるアルゴリズムを研究する。 我々の貢献は、2人のプレイヤーゼロサムゲームにおける平衡解法および強化学習へのアプローチとしての磁気ミラー降下の利点を実証することである。
  論文  参考訳（メタデータ） (2022-06-12T19:49:14Z)
• Controlling the Complexity and Lipschitz Constant improves polynomial nets [55.121200972539114]
  多項式ネットの結合CP分解(CCP)モデルとNested Coupled CP分解(NCP)モデルに対する新しい複雑性境界を導出する。 本研究では、6つのデータセットで実験的に評価し、モデルが逆摂動に対して頑健であるとともに精度も向上することを示す。
  論文  参考訳（メタデータ） (2022-02-10T14:54:29Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。 MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
  論文  参考訳（メタデータ） (2021-10-07T09:38:15Z)

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

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