Algebra Seminar talk
2018-11-09 (13:30)
Alexandr Kazda (Charles University Prague)
Wonderland of Reflections for Weighted Clones
Abstract:
Weighted clones describe the complexity of valued constraint
satisfaction problem (VCSP) with fixed constraint language. While it is
already known which languages of constraints give rise to polynomial
solvable or NP-hard VCSP problems (Kolmogorov, Krokhin, Rolínek, 2015)
and there is a theory of varieties for weighted algebras (Kozik,
Ochremiak, 2015), the algebraic side of VCSP is still not fully
explored. We will show that reflections of weighted clones give rise to
computational reductions between VCSP languages.