Descriptive Complexity of Constraints: An Algebraic Approach

约束满足问题在计算机科学中得到了广泛的研究，因为它可以对许多计算问题进行建模。这类问题通常在计算上很困难，但一些限制可以确保较低的复杂性。描述问题的复杂性是通过描述问题所需的逻辑语言的丰富性来衡量的。众所周知，低描述复杂性(即在相对弱的逻辑语言中的可定义性)意味着低计算复杂性(即求解问题所需的相对较少的计算资源)，我们提出使用逻辑编程语言Datalog及其片段来研究约束约束满足问题的描述复杂性。这应该会导致更好地理解需要少量空间来解决的约束满足问题。我们计划结合代数、逻辑和组合学的方法来刻画描述复杂性较低的约束满足问题。

Constraint satisfaction problems have been widely studied in computer science because they can model many computational problems. Such problems are computationally hard in general, but some restrictions may ensure lower complexity. Descriptive complexity of a problem is measured by the richness of logical language necessary to describe the problem. As is well known, low descriptive complexity (that is, definability in a relatively weak logical language) implies low computational complexity (that is, relatively small amount of computational resources necessary to solve the problem).We propose to study descriptive complexity of restricted constraint satisfaction problems using the logic programming language Datalog and its fragments. This should lead to a better understanding of constraint satisfaction problems that require a small amount of space to solve them. We plan to combine methods from algebra, logic, and combinatorics to characterise constraint satisfaction problems with low descriptive complexity.