Tractability and Learnability Arising from Algebras with Few Subpowers
Authors:
- PaweŁ IdziakPIPaweŁ Idziak
- Petar MarkovićPMPetar Marković
- Ralph McKenzieRMRalph McKenzie
- Matthew ValerioteMVMatthew Valeriote
- Ross WillardRWRoss Willard
Top Cited Papers
- 1 January 2010
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 39 (7) , 3023-3037
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.
Keywords
This publication has 25 references indexed in Scilit:
- Varieties with few subalgebras of powersTransactions of the American Mathematical Society, 2009
- CD(4) has bounded widthAlgebra universalis, 2009
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)SIAM Journal on Computing, 2009
- Learning intersection-closed classes with signaturesTheoretical Computer Science, 2007
- A Simple Algorithm for Mal'tsev ConstraintsSIAM Journal on Computing, 2006
- A dichotomy theorem for constraint satisfaction problems on a 3-element setJournal of the ACM, 2006
- The expressive rate of constraintsAnnals of Mathematics and Artificial Intelligence, 2005
- Classifying the Complexity of Constraints Using Finite AlgebrasSIAM Journal on Computing, 2005
- Learnability of quantified formulasTheoretical Computer Science, 2003
- When Won′t Membership Queries Help?Journal of Computer and System Sciences, 1995