DocumentCode :
728993
Title :
Locally Finite Constraint Satisfaction Problems
Author :
Klin, Bartek ; Kopczynski, Eryk ; Ochremiak, Joanna ; Torunczyk, Szymon
Author_Institution :
Univ. of Warsaw, Warsaw, Poland
fYear :
2015
fDate :
6-10 July 2015
Firstpage :
475
Lastpage :
486
Abstract :
First-order definable structures with atoms are infinite, but exhibit enough symmetry to be effectively manipulated. We study Constraint Satisfaction Problems (CSPs) where both the instance and the template are definable structures with atoms. As an initial step, we consider locally finite templates, which contain potentially infinitely many finite relations. We argue that such templates occur naturally in Descriptive Complexity Theory. We study CSPs over such templates for both finite and infinite, definable instances. In the latter case even decidability is not obvious, and to prove it we apply results from topological dynamics. For finite instances, we show that some central results from the classical algebraic theory of CSPs still hold: the complexity is determined by polymorphisms of the template, and the existence of certain polymorphisms, such as majority or Maltsev polymorphisms, guarantees the correctness of classical algorithms for solving finite CSP instances.
Keywords :
algebra; constraint satisfaction problems; set theory; CSP; Maltsev polymorphisms; algebraic theory; descriptive complexity theory; locally finite constraint satisfaction problems; locally finite templates; Color; Complexity theory; Cost accounting; Orbits; Polynomials; Standards; Upper bound; Constraint Satisfaction Problems; Sets with atoms;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Logic in Computer Science (LICS), 2015 30th Annual ACM/IEEE Symposium on
Conference_Location :
Kyoto
ISSN :
1043-6871
Type :
conf
DOI :
10.1109/LICS.2015.51
Filename :
7174905
Link To Document :
بازگشت