Descriptive Complexity of Constraints: An Algebraic Approach

点击翻译按钮获取中文摘要

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.