On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction

The universal-algebraic approach has proved a powerful tool in the study of the computational complexity of constraint satisfaction problems (CSPs). This approach has previously been applied to the study of CSPs with finite or (infinite) ω-categorical templates, and relies on two facts. The first is that in finite or ω-categorical structures A, a relation is primitive positive definable if and only if it is preserved by the polymorphisms of A. The second is that every finite or ω-categorical structure is homomorphically equivalent to a core structure. In this paper, we present generalizations of these facts to infinite structures that are not necessarily ω-categorical. Specifically, we prove that every CSP can be formulated with a template A such that a relation is primitive positive definable in A if and only if it is firstorder definable in A and preserved by the infinitary polymorphisms of A. Using existential positive closure we rederive and extend known results about cores, presenting the new notions of core theories (models of which will be cores) and core companions (which are defined analogously to model companions in model theory). We prove a uniqueness result for core companions that yields the uniqueness of model-complete cores of ω-categorical structures. Existential positive closure is also the crucial concept to give an exact characterization of those CSPs that can be formulated with (a finite or) an ω-categorical template.