Publication at Faculty of Mathematics and Physics |
2007
Abstract
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 omega-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.