UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Generalized satisfiability problems via operator assignments

Atserias, A; Kolaitis, PG; Severini, S; (2019) Generalized satisfiability problems via operator assignments. Journal of Computer and System Sciences , 105 pp. 171-198. 10.1016/j.jcss.2019.05.003. (In press). Green open access

[thumbnail of Severini 1-s2.0-S0022000019300406-main.pdf]
Preview
Text
Severini 1-s2.0-S0022000019300406-main.pdf - Published version

Download (842kB) | Preview

Abstract

Schaefer introduced a framework for generalized satisfiability problems on the Boolean domain and characterized the computational complexity of such problems. We investigate an algebraization of Schaefer’s framework in which the Fourier transform is used to represent constraints by multilinear polynomials in a unique way. This representation of constraints gives rise to a relaxation of the notion of satisfiability in which the values to variables are linear operators on some Hilbert space. For constraints given by a system of linear equations over the two-element field, earlier work in the foundations of quantum mechanics has shown that there are systems that have no solutions in the Boolean domain, but have solutions via operator assignments on some finite-dimensional Hilbert space. Our main result is a complete characterization of the classes of Boolean relations for which there is a gap between satisfiability in the Boolean domain and the relaxation of satisfiability via operator assignments.

Type: Article
Title: Generalized satisfiability problems via operator assignments
Open access status: An open access version is available from UCL Discovery
DOI: 10.1016/j.jcss.2019.05.003
Publisher version: https://doi.org/10.1016/j.jcss.2019.05.003
Language: English
Additional information: This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Keywords: Constraint satisfaction problem, Quantum satisfiability, Non-local games, Dichotomy theorems, Linear operators, Undecidable problems, pp-Definitions
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/1562092
Downloads since deposit
37Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item