FG1 Seminar talk
Alexandr Kazda (Charles University Prague)
Wonderland of Reflections for Weighted Clones
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.