論文の概要: RE-completeness of entangled constraint satisfaction problems

• arxiv url: http://arxiv.org/abs/2410.21223v2
• Date: Tue, 25 Feb 2025 19:23:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-27 15:24:46.086819
• Title: RE-completeness of entangled constraint satisfaction problems
• Title（参考訳）: 絡み合った制約満足度問題の再完全性
• Authors: Eric Culf, Kieran Mastel,
• Abstract要約: シェーファーの二分法定理は、CSP言語が効率的に決定可能であるかNP完全であることを示す。 CSP言語を非局所ゲームの公式性を用いて量子代入に拡張することは可能である。 簡潔に提示されていない場合でもCSP言語は決定不能であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Constraint satisfaction problems (CSPs) are a natural class of decision problems where one must decide whether there is an assignment to variables that satisfies a given formula. Schaefer's dichotomy theorem, and its extension to all alphabets due to Bulatov and Zhuk, shows that CSP languages are either efficiently decidable, or NP-complete. It is possible to extend CSP languages to quantum assignments using the formalism of nonlocal games. Due to the equality of complexity classes MIP$^\ast=$ RE, general succinctly-presented entangled CSPs are RE-complete. In this work, we show that a wide range of NP-complete CSPs become RE-complete in this setting, including all boolean CSPs, such as 3SAT, as well as $3$-colouring. This also implies that these CSP languages remain undecidable even when not succinctly presented. To show this, we work in the weighted algebra framework introduced by Mastel and Slofstra, where synchronous strategies for a nonlocal game are represented by tracial states on an algebra. Along the way, we improve the subdivision technique in order to be able to separate constraints in the CSP while preserving constant soundness, construct commutativity gadgets for all boolean CSPs, and show a variety of relations between the different ways of presenting CSPs as games.
• Abstract（参考訳）: 制約満足度問題 (Constraint satisfaction problem, CSP) は、与えられた式を満たす変数への代入があるかどうかを判断しなければならない決定問題の自然クラスである。 シェーファーの二分法定理とブラートフやチュークによる全てのアルファベットへの拡張は、CSP言語が効率的に決定可能であるかNP完全であることを示す。 CSP言語を非局所ゲームの公式性を用いて量子代入に拡張することは可能である。 複雑性クラス MIP$^\ast=$ RE の等式のため、一般的な簡潔に表現された絡み合った CSP は再完備である。 本研究は,3SAT などのブール CSP や 3$-colouring など,幅広い NP 完全 CSP が再完全となることを示す。 これはまた、簡潔に提示されていなくてもこれらのCSP言語は決定不能であることを意味している。 これを示すために、Mastel と Slofstra が導入した重み付き代数フレームワークにおいて、非局所ゲームに対する同期戦略は代数上のトランザクショナル状態によって表される。 その過程で,定音性を保ちながらCSPの制約を分離し,全てのブール系CSPに対して可換性のあるガジェットを構築し,CSPをゲームとして提示する方法の多様さを示す。

関連論文リスト

• Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction [44.67050228129961]
  制約満足度問題(CSP)のためのトランスフォーマーベースのフレームワークを提案する。 CSPは多くのアプリケーションで利用されており、機械学習によるソリューションの高速化は幅広い関心を集めている。 本稿では,Transformerをソリューションリファインダとして活用する自己教師型フレームワークであるConsFormerを提案する。
  論文  参考訳（メタデータ） (2025-02-18T16:51:01Z)
• Applying the quantum approximate optimization algorithm to general constraint satisfaction problems [0.0]
  ランダム制約満足度問題(CSP)に適用した場合に量子近似最適化(QAOA)の性能を解析するための理論的手法を開発する。 提案手法により,ランダムに生成されたCSPのインスタンスに適用した場合に,各レイヤとパラメータを用いてQAOAの成功確率を計算することができる。 ランダムな$k$-SATは、QAOAを用いた量子古典的分離を示す上で、これらのCSPの中で最も有望であると考えられる。
  論文  参考訳（メタデータ） (2024-11-26T14:00:34Z)
• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。 特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T00:34:56Z)
• CSPs with Few Alien Constraints [12.330326247154968]
  CSP$(mathcalA cup mathcalB)$ ここで$mathcalA$は構造、$mathcalB$は異方構造である。 我々は、以前分類の試みを免れたいくつかのよく研究された問題に対して、接続を確立し、転送可能な複雑性結果を得る。
  論文  参考訳（メタデータ） (2024-08-23T08:34:13Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Satisfiability of commutative vs. non-commutative CSPs [2.07180164747172]
  NP-ハード CSP は、有限次元および無限次元ヒルベルト空間上の作用素を通して古典的満足度と満足度を分離することを示す。 また,非有界幅のトラクタブル CSP は,いかなる種類の満足感ギャップも持たないことを示した。
  論文  参考訳（メタデータ） (2024-04-17T19:26:50Z)
• Approximation algorithms for noncommutative CSPs [0.0]
  非可換制約満足問題(NC-CSP)は古典的CSPの高次元作用素拡張である。 量子情報においてその重要性にもかかわらず、その近似性はほとんど未解明のままである。 近似等長、相対分布、および$ast$-anticommutationという3つの主要な概念を導入する。
  論文  参考訳（メタデータ） (2023-12-28T01:22:27Z)
• Nonlocality under Computational Assumptions [51.020610614131186]
  相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。 ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
  論文  参考訳（メタデータ） (2023-03-03T16:53:30Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction [1.9813182042770607]
  本稿では,制約満足度問題(CSP)のエンドツーエンド探索としてトレーニング可能な汎用グラフニューラルネットワークアーキテクチャを提案する。 我々のアーキテクチャは、純粋にデータ駆動方式で任意のCSPに問題固有のものを生成するために、ポリシー勾配降下で教師なしで訓練することができる。
  論文  参考訳（メタデータ） (2022-08-22T12:09:19Z)
• OrdinalCLIP: Learning Rank Prompts for Language-Guided Ordinal Regression [94.28253749970534]
  我々は、リッチなセマンティックCLIP潜在空間からランクの概念を学ぶことを提案する。 OrdinalCLIPは学習可能なコンテキストトークンと学習可能なランク埋め込みで構成されている。 実験結果から,本パラダイムは一般順序回帰タスクにおける競合性能を達成できることが示唆された。
  論文  参考訳（メタデータ） (2022-06-06T03:54:53Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。 我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
  論文  参考訳（メタデータ） (2022-02-10T18:59:52Z)
• Poly-NL: Linear Complexity Non-local Layers with Polynomials [76.21832434001759]
  性能を損なわずに2次から線形に複雑性を低減できる新しい高速非局所ブロックを定式化する。 The proposed method, we dub that "Poly-NL" is competitive to state-of-the-art performance across image recognition, instance segmentation, and face detection task。
  論文  参考訳（メタデータ） (2021-07-06T19:51:37Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。 量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。 我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
  論文  参考訳（メタデータ） (2021-06-11T18:00:09Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS [68.419966284392]
  本研究では,有界凸多面体領域上でグラディエントDescentを実行することで解くことができる探索問題について検討する。 このクラスは、PPAD と PLS の2つのよく知られたクラスの交叉に等しいことを示す。
  論文  参考訳（メタデータ） (2020-11-03T18:58:51Z)
• Convex Polytope Trees [57.56078843831244]
  コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。 木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
  論文  参考訳（メタデータ） (2020-10-21T19:38:57Z)

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

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