Tractability and learnability arising from algebras with few subpowers

摘要

A constraint language γ on a finite set A has been called polynomially expressive if the number of n-ary relations expressible by ?∧-atomic formulas over Γ 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 Γ 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 Γ under ?∧-atomic expressibility) is globally tractable. We also show that the set of relations definable over Γ using quantified generalized formulas is polynomially exactly learnable using improper equivalence queries.