Tractability and learnability arising from algebras with few subpowers

Abstract

A k-edge operation phi on a finite set A is a k + 1-ary operation that satisfies the identities phi (x,x,y,...,y) ap phi(x,y,x,y,...,y) ap y, phi(y,y,y,x,y,...,y) ap phi(y,y,y,y,x,y,...,y) ap ... ap ... phi(y,y,y,...,y,x) ap y. We prove that any constraint language .. that, for some k > 1, has a k-edge operation as a polymorphism is globally tractable. We also show that the set of relations definable over Gamma using quantified generalized formulas is polynomially exactly learnable using improper equivalence queries. Special instances of k-edge operations are Mal'cev and near-unanimity operations and so this class of constraint languages includes many well known examples.