Loading...
Loading...

Go to the content (press return)

Generalized satisfiability problems via operator assignments

Author
Atserias, A.; Kolaitis, Ph.; Severini, S.
Type of activity
Journal article
Journal
Journal of computer and system sciences
Date of publication
2019-11
Volume
105
First page
171
Last page
198
DOI
10.1016/j.jcss.2019.05.003
Project funding
A unified theory of algorithmic relaxations
Theory and applications in satisfiability and constraint optimization
Repository
http://hdl.handle.net/2117/134848 Open in new window
URL
https://www.sciencedirect.com/science/article/pii/S0022000019300406 Open in new window
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 c...
Citation
Atserias, A.; Kolaitis, P.; Severini, S. Generalized satisfiability problems via operator assignments. "Journal of computer and system sciences", vol. 105, Novembre 2019, p. 171-198.
Keywords
Constraint satisfaction problem, Dichotomy theorems, Linear operators, Non-local games, Quantum satisfiability, Undecidable problems, pp-definitions
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

  • Atserias, Albert  (author)
  • Kolaitis, Phokion  (author)
  • Severini, Simone  (author)

Attachments