論文の概要: RE-completeness of entangled constraint satisfaction problems
- arxiv url: http://arxiv.org/abs/2410.21223v1
- Date: Mon, 28 Oct 2024 17:05:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-29 12:22:03.965778
- Title: RE-completeness of entangled constraint satisfaction problems
- Title（参考訳）: 絡み合った制約満足度問題の再完全性
- Authors: Eric Culf, Kieran Mastel,
- Abstract要約: シェーファーの定理は、CSP言語が効率的に決定可能であるかNP完全であることを示す。
CSP言語を非局所ゲームの公式性を用いて量子代入に拡張することは可能である。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- 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 become 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, and all CSPs with two variables per constraint ($2$-CSPs), such as $k$-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, and we show a variety of relations between the different ways of presenting CSPs as games. In particular, we show that all $2$-CSP games are oracularizable, wherein the two players' operators for questions asked at the same time must commute for a perfect strategy.
- Abstract（参考訳）: 制約満足度問題 (Constraint satisfaction problem, CSP) は、与えられた式を満たす変数への代入があるかどうかを判断しなければならない決定問題の自然クラスである。
シェーファーの二分法定理とブラートフやチュークによる全てのアルファベットへの拡張は、CSP言語が効率的に決定可能であるかNP完全であることを示している。
CSP言語を非局所ゲームの公式性を用いて量子代入に拡張することは可能である。
複雑性クラス MIP$^\ast=$ RE の等式のため、一般的な簡潔に表現された絡み合った CSP は再完備となる。
本研究は,3SAT などすべてのブール CSP や$k$-colouring など,制約ごとに2変数(2$-CSP) を持つすべての CSP を含む,幅広いNP完全 CSP が再完全となることを示す。
これはまた、簡潔に提示されていなくてもこれらのCSP言語は決定不能であることを意味している。
これを示すために、Mastel と Slofstra が導入した重み付き代数フレームワークにおいて、非局所ゲームに対する同期戦略は代数上のトランザクショナル状態によって表される。
その過程で,音質を一定に保ちながらCSPの制約を分離できるように分割手法を改良し,ゲームとしてCSPを提示する方法の異なる関係を示す。
特に,2ドルのCSPゲームはすべてオラキュラライズ可能であることを示す。
関連論文リスト
- 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) - Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。
量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。
我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
論文 参考訳（メタデータ） (2021-06-11T18:00:09Z) - The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS [68.419966284392]
本研究では,有界凸多面体領域上でグラディエントDescentを実行することで解くことができる探索問題について検討する。
このクラスは、PPAD と PLS の2つのよく知られたクラスの交叉に等しいことを示す。
論文 参考訳（メタデータ） (2020-11-03T18:58:51Z) - Complexity Aspects of Fundamental Questions in Polynomial Optimization [3.42658286826597]
P=NPがなければ、二次プログラムの局所最小値のユークリッド距離内の点を見つけるSDPは存在しないことを示す。
また、最適値が有限であるプログラムが最適解を持つか否かをテストすることはNPハードであることを示す。
最終章では,SDPの階層化に寄与する強制力の特性について紹介する。
論文 参考訳（メタデータ） (2020-08-27T14:58:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。