Constraint Satisfaction Problems over Finite Structures

Publikationstyp
Conference Paper
Date Issued
2021-06-29
Sprache
English
Author(s)
Barto, Libor  
Demeo, William  
Mottet, Antoine  
TORE-URI
http://hdl.handle.net/11420/12076
Volume
2021-June
Article Number
9470670
Citation
36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021)
Contribution to Conference
36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021  
Publisher DOI
10.1109/LICS52264.2021.9470670
Scopus ID
2-s2.0-85113867384
We initiate a systematic study of the computational complexity of the Constraint Satisfaction Problem (CSP) over finite structures that may contain both relations and operations. We show the close connection between this problem and a natural algebraic question: which finite algebras admit only polynomially many homomorphisms into themWe give some sufficient and some necessary conditions for a finite algebra to have this property. In particular, we show that every finite equationally nontrivial algebra has this property which gives us, as a simple consequence, a complete complexity classification of CSPs over two-element structures, thus extending the classification for two-element relational structures by Schaefer (STOC'78).We also present examples of two-element structures that have bounded width but do not have relational width (2,3), thus demonstrating that, from a descriptive complexity perspective, allowing operations leads to a richer theory.