InfCSP · Descriptive Complexity of Infinite Domain Constraint Satisfaction Problems

Descriptive Complexity of Infinite Domain Constraint Satisfaction Problems

The constraint satisfaction problem is a computational problem where the input consists of a set of variables and a set of constraints, and the goal is to decide whether there exists an assignment of values to the variables satisfying all the constraints. This simple framework captures many computational problems such as satisfiability, graph colouring or solving systems of equations. The unified formulation allows for analysing such problems globally, instead of studying each problem in isolation. Intense efforts to understand the complexity of constraint satisfaction problems with a finite set of values culminated recently in the confirmation of the famous Dichotomy Conjecture - it has been shown that every problem of this kind is either NP-complete or solvable in polynomial time. However, for many problems which appear naturally in different areas of computer science, such as combinatorial optimisation, artificial intelligence, scheduling and computational biology, the scenario where the set of possible values is finite is too restricted. The overall objective of this project was to exploit the consequences of symmetries to understand the power of logic-based approaches to the infinite domain constraint satisfaction problem - a version of the constraint satisfaction problem where the set of possible values is infinite. The project, taking place at the interface of mathematics and computer science, advanced the research on symmetric computation and strengthened collaborations between the University of Cambridge and other world-leading institutions in the field.

Текст от CORDIS, на английски · Данни: CORDIS, © Европейски съюз