RE-completeness of entangled constraint satisfaction problems

• URL: http://arxiv.org/abs/2410.21223v1
• Date: Mon, 28 Oct 2024 17:05:58 GMT
• Title: RE-completeness of entangled constraint satisfaction problems
• Authors: Eric Culf, Kieran Mastel,
• Abstract summary: Schaefer's theorem 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.
• Score: 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.

Related papers

• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  We prove lower bounds for computing a near-optimal $T$-sparse CCE. In particular, we show that the inapproximability of maximum clique precludes attaining any non-trivial sparsity in time.
  arXiv  Detail & Related papers  (2024-11-04T00:34:56Z)
• CSPs with Few Alien Constraints [12.330326247154968]
  We consider CSP$(mathcalA cup mathcalB)$ where $mathcalA$ is a structure and $mathcalB$ is an alien structure. We establish connections and obtain transferable complexity results to several well-studied problems that previously escaped classification attempts.
  arXiv  Detail & Related papers  (2024-08-23T08:34:13Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Satisfiability of commutative vs. non-commutative CSPs [2.07180164747172]
  We show that NP-hard CSPs admit a separation between classical satisfiability and satisfiability via operators on finite- and infinite-dimensional Hilbert spaces. We also show that tractable CSPs of unbounded width have no satisfiability gaps of any kind.
  arXiv  Detail & Related papers  (2024-04-17T19:26:50Z)
• Approximation algorithms for noncommutative CSPs [0.0]
  Noncommutative constraint satisfaction problems (NC-CSPs) are higher-dimensional operator extensions of classical CSPs. Despite their significance in quantum information, their approximability remains largely unexplored. We introduce three key concepts: approximate isometry, relative distribution, and $ast$-anticommutation.
  arXiv  Detail & Related papers  (2023-12-28T01:22:27Z)
• Nonlocality under Computational Assumptions [51.020610614131186]
  A set of correlations is said to be nonlocal if it cannot be reproduced by spacelike-separated parties sharing randomness and performing local operations. We show that there exist (efficient) local producing measurements that cannot be reproduced through randomness and quantum-time computation.
  arXiv  Detail & Related papers  (2023-03-03T16:53:30Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction [1.9813182042770607]
  We propose a universal Graph Neural Network architecture which can be trained as an end-2-end search for any Constraint Satisfaction Problem (CSP) Our architecture can be trained unsupervised with policy gradient descent to generate problem specifics for any CSP in a purely data driven manner.
  arXiv  Detail & Related papers  (2022-08-22T12:09:19Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS [68.419966284392]
  We study search problems that can be solved by performing Gradient Descent on a bounded convex polytopal domain. We show that this class is equal to the intersection of two well-known classes: PPAD and PLS.
  arXiv  Detail & Related papers  (2020-11-03T18:58:51Z)
• Complexity Aspects of Fundamental Questions in Polynomial Optimization [3.42658286826597]
  We show that unless P=NP, there cannot be a SDP that finds a point within Euclidean distance of a local minimum of a quadratic program. We also show that testing whether aally constrained program with a finite optimal value has an optimal solution is NP-hard. In our final chapter, we present an characterization of coercives that lends itself to a hierarchy of SDPs.
  arXiv  Detail & Related papers  (2020-08-27T14:58:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.