Manuel Bodirsky
Quantified Equality Constraints
With Hubie Chen. Accepted for publication in SIAM Journal on Computing. An extended abstract appeared in the proceedings of the Annual IEEE Symposium on Logic in Computer Science (LICS07)
Abstract
An equality template (also equality constraint language ) is a relational structure with infinite universe whose relations can be defined by boolean combinations of equalities. We prove a complete complexity classification for quantified constraint satisfaction problems (QCSPs) over equality templates: these problems are in L (decidable in logarithmic space), NP-complete, or PSPACE-complete. To establish our classification theorem we combine methods from universal algebra with concepts from model theory.
Download
Download: the journal version of this paper is available in pdf.
Remarks and Related Papers
Some results in this paper build upon previous work with Jan Kara about the complexity of the CSP for equality constraint languages. We also use a result for infinite-domain quantified constraint satisfaction from this paper. The class of all equality constraint languages has been studied in greater detail in a joint paper with Michael Pinsker.
