A preservation theorem for valued structures

The algebraic approach to constraint satisfaction problems (CSPs) has been very fruitful for classifying computational complexity. This approach is based on the interplay of polymorphisms, which are operations that preserve all relations of the CSP template, and of relations that are primitively positively definable in the template. A central result in the area is the so-called preservation theorem, due to Bodirsky and Nešetřil for infinite-domain templates, which states that a relation is primitively positively definable in a relational structure A if and only if it is preserved by all polymorphisms of A. Valued CSPs are a natural generalization of CSPs that allows to model optimization problems by replacing relations in the template by cost functions. For valued CSPs over finite-domain templates a preservation theorem was proved by Fulla and Živný, using the more general concepts of fractional polymorphisms and expressibility instead of polymorphisms and primitive positive definability. The focus of this talk is an ongoing project towards a common generalization of the result of Bodirsky and Nešetřil and of Fulla and Živný for valued CSPs over infinite-domain templates. We conjecture that given a valued structure Γ with an oligomorphic automorphism group, a valued relation R is expressible in Γ if and only if R is improved by all fractional polymorphisms of Γ. If true, this result would have far-reaching consequences related to the complexity of valued CSPs and to the algebraic structure of templates for valued CSPs, e.g., existence of cores.

DDC Class

510: Mathematics

Options

A preservation theorem for valued structures