Semanisinova, Z., Bodirsky, M., Jahel, C., & Mottet, A. (2026, February 6). A Preservation Theorem for Valued Structures [Conference Presentation]. 108th Workshop on General Algebra, Wien, Austria. http://hdl.handle.net/20.500.12708/226456
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.
en
Project title:
Komplexität von Optimierung: VCSPs auf unendlichen Mengen: ESP6949724 (FWF - Österr. Wissenschaftsfonds)
-
Project (external):
European Research Council
-
Project ID:
ERC Synergy Grant 101071674
-
Research Areas:
Logic and Computation: 20% Fundamental Mathematics Research: 80%