Fully symmetric operations

Abstract

Problém splnitelnosti omezujících podmínek nad algebrou A je řešitelný pomocí základní relaxace lineárního programování právě tehdy, když má A symetrické termové operace všech arit. Není však jasné, jak rozhodnout, zda daná algebra tuto podmínku splňuje. V této práci dokazujeme, že tříprvková algebra, která má omezenou šířku a která obsahuje symetrické termové operace arit 1,2,3, už má nutně symetrické termové operace všech arit. i

The Constraint Satisfaction Problem over an algebra A is solvable by the basic linear programming relaxation if, and only if, A has a symmetric term operation of every arity. It is, however, unclear how to decide that the latter condition is satisfied for a given algebra. In this thesis, we prove that a three-element algebra, which has bounded width and a symmetric term operation of arities 1,2, and 3, necessarily has a symmetric term operation of every arity. i