Generalized satisfiability problems via operator assignments

DOI10.1016/j.jcss.2019.05.003zbMath1423.68430arXiv1704.01736OpenAlexW2944932268WikidataQ127838268 ScholiaQ127838268MaRDI QIDQ5919560

Albert Atserias, Phokion G. Kolaitis, Simone Severini

Publication date: 7 August 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1704.01736

zbMATH Keywords

linear operatorsconstraint satisfaction problemdichotomy theoremsnon-local gamesundecidable problemspp-definitionsquantum satisfiability

Mathematics Subject Classification ID

Quantum computation (81P68) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Special classes of linear operators (47B99)

Cites Work

• Twisted strong Macdonald theorems and adjoint orbits
• A combinatorial approach to nonlocality and contextuality
• Closed systems of functions and predicates
• Quantum logic is undecidable
• Perfect commuting-operator strategies for linear system games
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Simple unified form for the major no-hidden-variables theorems
• Analysis of Boolean Functions
• Characterization of Binary Constraint System Games
• The complexity of satisfiability problems
• On the Problem of Hidden Variables in Quantum Mechanics
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Logic for computer scientists
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Generalized satisfiability problems via operator assignments