Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/28520
Title: | Tractability and Learnability Arising from Algebras with Few Subpowers | Authors: | Idziak Paweł Marković Petar McKenzie Ralph Valeriote Matthew Willard Ross |
Keywords: | constraint satisfactionlearnabilitycomplexitypolymorphismMal'cevnear-unanimitypolynomially expressivefew subpowers | Issue Date: | 2010 | Journal: | SIAM Journal on Computing / Society for Industrial and Applied Mathematics | Abstract: | A constraint language $\Gamma$ on a finite set A has been called polynomially expressive if the number of n-ary relations expressible by $\exists\wedge$-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 $\langle\Gamma\rangle$ (the closure of $\Gamma$ under $\exists\wedge$-atomic expressibility) 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. | URI: | https://open.uns.ac.rs/handle/123456789/28520 | ISSN: | 0097-5397 | DOI: | 10.1137/090775646 |
Appears in Collections: | PMF Publikacije/Publications |
Show full item record
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.