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).
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 |
Archive Staff Only
 |
View Item |
