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... for some constant k. It has recently been discovered that this property is characterized by the existence of a (k + 1)-ary...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 2010-01, Vol.39 (7-8), p.3023-3037
Main Authors: IDZIAK, Pawel, MARKOVIC, Petar, MCKENZIE, Ralph, VALERIOTE, Matthew, WILLARD, Ross
Format: Article
Language:English
Subjects:
Algebra
Algorithms
Applied sciences
Computation
Computer science
control theory
systems
Exact sciences and technology
Mathematical analysis
Mathematical problems
Miscellaneous
Polymorphism
Queries
Studies
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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... 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 [left angle bracket]Γ[right angle bracket] (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. [PUBLICATION ABSTRACT]
ISSN:0097-5397
1095-7111
DOI:10.1137/090775646