## Paper: Quantified Equality Constraints (at LICS 2007)

**Manuel Bodirsky Hubie Chen**

### 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.

### BibTeX

@InProceedings{BodirskyChen-QuantifiedEqualityC, author = {Manuel Bodirsky and Hubie Chen}, title = {Quantified Equality Constraints}, booktitle = {Proceedings of the Twenty-Second Annual IEEE Symposium on Logic in Computer Science (LICS 2007)}, year = {2007}, month = {July}, pages = {203--212}, location = {Wroclaw, Poland}, publisher = {IEEE Computer Society Press} }