TRACTABILITY AND LEARNABILITY ARISING FROM ALGEBRAS WITH FEW SUBPOWERS
A constraint language Gamma on a finite set A has been called polynomially expressive if the number of n-ary relations expressible by there exists Lambda-atomic formulas over Gamma is bounded by exp(O(n(k))) for some constant k. It has recently been discovered that this property is characterized by the existence of a (k + 1)-ary polymorphism satisfying certain identities; such polymorphisms are called k-edge operations and include Mal'cev and near-unanimity operations as special cases. We prove that if Gamma is any constraint language which, for some k > 1, has a k-edge operation as a polymorphism, then the constraint satisfaction problem for   (the closure of Gamma under there exists Lambda-atomic expressibility) is globally tractable. We also show that the set of relations definable over G using quantified generalized formulas is polynomially exactly learnable using improper equivalence queries.
learnability few subpowers polynomially expressive polymorphism mal'cev near-unanimity constraint satisfaction complexity