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?

In studying the landscape of infinite-domain CSPs, our immediate impact is in Computational Complexity. Positive results have the strongest impact, where we find the applicability of algorithms for interesting problems, where these were not known before.

Our research is theoretical in nature, so much of the benefit in understanding our complexity landscape may not immediately have a great influence in areas of application. Nonetheless, the goals of the project remain focused towards problems rooted in areas where they are of great practical interest. We will consider separately the areas in which our results might have an impact.

Linear programming can be reduced to its feasibility question which is well-known to be solvable in polynomial time. Integer program feasibility is already NP-complete. It is important to understand how much more expressive power can be added to linear program feasibility while maintaining its tractability, just as it is to know how little can be removed from integer program feasibility before reaching tractability.

We wish to know how linear and integer programming are used in practice, to guide the types of enriching and detracting that we need to find. For example, much practical solving of linear programs uses the simplex method, whose worse-case complexity is exponential (though there are also known to be feasible instances on which simplex is not practical). In order to guide us in this matter we will meet with Dr. Paul Kerr-Delworth at MathWorks (the makers of Matlab), in Cambridge, as he is an expert in industrial applications of mixed integer programming (MIP). MIP has diverse application, from Economics to Telecommunications to Chemical Engineering. We will seek out the types of MIP that are most useful in practice, that we might look for efficient algorithms; as well as addressing how we might best code the tractable extensions we know for use in commercial software. We will make four visits to MathWorks at six-monthly intervals from the start of the grant.

Some of the oldest results in CSPs relate to infinite-domain problems driven by applications in Artificial Intelligence. In temporal reasoning, the important formalism of Allen's interval algebra was known to be a CSP that is in general NP-complete. Of great significance was the discovery of the maximal tractable fragment Ord-Horn (which can be said to truly give a boundary of tractability). Discrete temporal reasoning, in which time points are modelled by the integers instead of the rationals, has only much more recently been systematically considered. There are many situations in which discrete time is essential to reasoning, for example scheduling problems and reasoning about sampled physical systems. In both of our discrete-time projects we seek to find the boundary of tractability. For the cases we know to be tractable, this amounts to establishing how much further the border can be pushed.

Generic methods for specific problems:

Max atoms. The problem of solving parity games is polynomially equivalent to model-checking the mu-calculus, which plays a central role in Verification. Puri gave a polynomial reduction of parity games to mean payoff games, and advocated the use of this algorithm for solving parity games. Max atoms, which is equivalent to Mean payoff games, is known neither to be in P nor NP-complete. Discovery of a polynomial algorithm would be very significant.

Integer factoring. This is of famously elusive complexity, known neither to be in P nor NP-hard. The RSA public-key cryptosystem works on the assumption that it is not in P. Integer factoring was recently given as a CSP, and we hope to gain insight into the complexity of this problem, even if we do not expect to solve it!

Finally, we wish to share our results and ideas with industrial partners and academics at a one-day workshop held at Middlesex.