Descriptive Complexity of Constraints: An Algebraic Approach

Lead Research Organisation: Durham University
Department Name: Computer Science

Abstract

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.

Publications

10 25 50
publication icon
Börner F (2009) The complexity of constraint satisfaction games and QCSP in Information and Computation

publication icon
Carvalho C (2010) Two new homomorphism dualities and lattice operations in Journal of Logic and Computation

publication icon
Carvalho C (2010) CSP duality and trees of bounded pathwidth in Theoretical Computer Science

publication icon
Egri L (2011) The Complexity of the List Homomorphism Problem for Graphs in Theory of Computing Systems

 
Description We investigated the solvability of various constraint satisfcation problems by means of logic programming language Datalog and its restrictions. We applied the algebraic machinery to give varipus sufficient conditions for the definability.
Exploitation Route Our findings might potentially be used for design of efficiemt constraint solvers or efficient database query processing languages.
Sectors Digital/Communication/Information Technologies (including Software)

 
Description No ecnomic or societal impact yet