Infinite-domain Constraint Satisfaction Problems

Lead Research Organisation: Middlesex University
Department Name: School of Science and Technology


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?

Planned Impact

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.
Description We have unlocked the computational complexity for a wide class of discrete temporal Constraint Satisfaction Problems that may be of interest in Artificial Intelligence (ICALP 2015). We are now in a position to attack some long-standing open questions from across Computer Science with the techniques we have developed.

We have shown algebraic properties through a relational method (LICS 2015) whose ethos has led to a remarkable new result (from Dmitriy Zhuk) in general algebra involving a certain polynomial-exponential gap in the sizes of minimal generating sets for algebra powers (see

We have additionally pushed the algebraic method for classifying the computational complexity of the Quantified Constraint Satisfaction Problems in new directions with our work in ICALP 2014.
Exploitation Route We have developed techniques that may be used to potentially understand several concrete problems whose computational complexity remains open and are widespread interest in Computer Science.
Sectors Digital/Communication/Information Technologies (including Software)

Description MathWorks Collaboration 
Organisation The Mathworks Ltd
Country United Kingdom 
Sector Private 
PI Contribution My contacts at MathWorks, with whom I have publications, guide my research on computational complexity of Mixed Integer Programming (MIP) in order to ensure that our focus on theoretical problems stays rooted in practical concerns. The contact who supports my EPSRC grant applications is Dr. Paul Kerr-Delworth, an expert in MIPs.
Collaborator Contribution My partners have kept me focused towards algorithms for industrial instances of infinite-domain Constraint Satisfaction Problems.
Impact Barnaby Martin, Jos Martin: The Complexity of Positive First-Order Logic without Equality II: The Four-Element Case. CSL 2010: 426-438. Barnaby Martin, Franco Raimondi, Taolue Chen, Jos Martin: The packing chromatic number of the infinite square lattice is less than or equal to 16. CoRR abs/1510.02374 (2015), submitted.
Start Year 2010