#	Pagina
attuale pagina	/open-h2020/projects/203242/results.html

Report

Teaser, summary, work performed and final results

Periodic Reporting for period 2 - CSP-Infinity (Homogeneous Structures, Constraint Satisfaction Problems, and Topological Clones)

Teaser

Summary

The project investigates the theoretical boundaries of efficient computation. Which computational problems can be solved with a reasonable amount of computational resources, and for which computational problems is this hopeless? We primarily study so-called constraint satisfaction problems, which is a very large class of problems that appear for example in scheduling, artificial intelligence, temporal and spatial reasoning, computational linguistics, phylogenetic reconstruction, and optimisation. The project explores the power of existing algorithmic paradigms (such as constraint propagation or least fixed point computation) but also develops powerful theoretical results that suggest that for some of the problems no efficient algorithm exists. A major aspect of the project are complete classifications for large classes of problems; these classifications indicate which problems are easy and which are hard to solve. Complexity classifications often lead to the discovery of completely new and unexpected polynomial-time algorithms. Such algorithms and more generally insights into the nature of polynomial-time computation has an impact in all of the application fields mentioned above.

Work performed

The project work concentrated on the following two directions: constraint satisfaction problems over `numeric domainsâ€™ such as the integers or the rationals, and `qualitativeâ€™ constraint satisfaction problems that resemble the well-studied constraint satisfaction problems over finite domains. In both of these directions, progress has been made concerning the fundamental theory of such problems in general, but also concerning the applications of the general theory to concrete classes of computational problems that are relevant in application areas. One example of such a class is the logic MMSNP, a fragment of existential second-order logic that is studied in knowledge representation and in database theory. We verified the so-called `tractability conjectureâ€™ for such problems using results from model theory, universal algebra, and Ramsey theory. Concerning numeric domains, we have applied the general theory to obtain a complete classification of the computational complexity for all constraint satisfaction problems that are definable over the order of the integers, covering CSPs that have been studied in scheduling.

Final results

Some of the challenges posed in the project description are still open:
one concerns for example a powerful extension of the logic MMSNP which has been called MMSNP2, aka guarded disjunctive Datalog: this is still a fragment of existential second-order logic, but now we can also quantify over relations and not just over sets. This logic allows to formulate many more queries that appear in Databases. Again, the goal is to verify the general tractability conjecture for infinite-domain CSPs. Since the general theory of infinite-domain CSPs advances rapidly, this is now within reach.

Another important goal arose from the work of the PI with the PhD Bertalan Bodor (ERC-funded):
it approaches the infinite-domain tractability conjecture by investigating the most symmetric constraint languages first. A mile-stone in this direction would be the verification of the infinite-domain tractability conjecture for all languages that have at most O(c2^(dn)) orbits on injective n-tuples, for all n (and constants c and d). We proved that these are precisely the structures that appear as reducts of finite covers of unary structures, which is a very concrete model-theoretic description that allows us to apply the universal-algebraic approach to constraint satisfaction.