Locally Finite Constraint Satisfaction Problems
Locally Finite Constraint Satisfaction Problems
复制标题
局部有限约束满足问题
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Szymon Toruńczyk
中科院分区：
文献类型：
--
作者：
Bartek Klin;Eryk Kopczynski;Joanna Ochremiak;Szymon Toruńczyk
原子的一阶可定义结构是无限的，但表现出足够的对称性，可以有效地操纵。研究了约束满足问题（csp），其中实例和模板都是可定义的原子结构。作为第一步，我们考虑局部有限模板，其中可能包含无限多个有限关系。我们认为这种模板在描述复杂性理论中是自然发生的。我们研究了有限和无限可定义实例的模板上的csp。在后一种情况下，甚至可判决性并不明显，为了证明它，我们应用了拓扑动力学的结果。对于有限实例，我们证明了经典CSP代数理论的一些中心结论仍然成立：复杂性是由模板的多态性决定的，并且某些多态性的存在，如多数多态性或Maltsev多态性，保证了经典算法求解有限CSP实例的正确性。
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.