Infinite-domain Constraint Satisfaction Problems

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

Constraint Satisfaction Problems (CSPs) provide a powerful framework within which to phrase many computational problems from across Computer Science. In Combinatorics they are known as Homomorphism Problems and in Databases they appear as conjunctive-query containment. CSPs manifest in Artificial Intelligence in the form of temporal and spatial reasoning, and in Computational Linguistics in the guise of tree description languages. In Computational Biology, phylogenetic reconstruction is a CSP, and in Graph Theory it known as H-colouring. We propose to study the computational complexity of CSPs given by a single constraint language that may have an infinite domain. Research into the finite-domain case is now quite advanced, yet a great many interesting problems, which may not be given as finite-domain CSPs, may be given as infinite-domain CSPs. For example, this is true for most of the CSPs associated with Artificial Intelligence and Computational Linguistics. The computational complexity of most natural finite-domain CSPs is now known, yet many interesting infinite-domain CSPs have open complexity. For example, this is true of the Max Atoms problem, very closely related to Model-checking the mu-calculus, a problem of open complexity from the Verification community. It is also true of the Concatenation problem for free algebras, a problem arising in the Rewriting community. Further, a CSP was recently given that is polynomially equivalent with the elusive problem of Integer factoring. The commonality of structure across CSPs gives hope that we might find generic methods with which to analyse the computational complexity of these diverse problems. We will work on these problems specifically, as well as seeking to map out landscapes of complexity in such areas as the following. Linear Programming. Linear program feasibility is well-known to be polynomial-time solvable, How much extra expressive power can be added to linear program feasibility while maintaining its tractability?Integer programming. Integer program feasibility is well-known to be (NP-)hard to solve. How little expressive power does one need to take away to reach tractability?