Maximal infinite-valued constraint languages

We systematically investigate the computational complexity of constraint satisfaction problems for constraint languages over an infinite domain. In particular, we study a generalization of the well-established notion of maximal constraint languages from finite to infinite domains. If the constraint language can be defined with an ω -categorical structure, then maximal constraint languages are in one-to-one correspondence to minimal oligomorphic clones. Based on this correspondence, we derive general tractability and hardness criteria for the corresponding constraint satisfaction problems.

Authors

• Manuel Bodirsky
• Hubie Chen
• Jan Kára
• Timo von Oertzen

Keywords

• Constraint satisfaction
• Computational complexity
• Universal algebra in computer science
• Countably categorical structures