Descriptive complexity of constraint problems
Repository URI
Repository DOI
Change log
Authors
Abstract
Constraint problems are a powerful framework in which many common combinatorial problems can be expressed. Examples include graph colouring problems, Boolean satisfaction, graph cut problems, systems of equations, and many more. One typically distinguishes between constraint satisfaction problems (CSPs), which model strictly decision problems, and so-called valued constraint satisfaction problems (VCSPs), which also include optimisation problems.
A key open problem in this field is the long-standing dichotomy conjecture
by Feder and Vardi. It claims that CSPs only fall into two categories:
Those that are NP-complete, and those that are solvable in polynomial time.
This stands in contrast to Ladner's theorem, which, assuming P
In this thesis, we approach the complexity of constraint problems from a descriptive complexity perspective. Namely, instead of studying the computational resources necessary to solve certain constraint problems, we consider the expressive power necessary to define these problems in a logic. We obtain several results in this direction. For instance, we show that Schaefer's dichotomy result for the case of CSPs over the Boolean domain can be framed as a definability result: Either a CSP is definable in fixed-point logic with rank (FPR), or it is NP-hard. Furthermore, we show that a dichotomy exists also in the general case. For VCSPs over arbitrary domains, we show that a VCSP is either definable in fixed-point logic with counting (FPC), or it is not definable in infinitary logic with counting.
We show that these definability dichotomies also have algorithmic implications.
In particular, using our results on the definability of VCSPs, we prove
a dichotomy on the number of levels in the Lasserre hierarchy necessary to obtain
an exact solution: For a finite-valued VCSP, either it is solved by the first
level of the hierarchy, or one needs
Finally, we explore how other methods from finite model theory can be useful in the context of constraint problems. We consider pebble games for finite variable logics in this context, and expose new connections between CSPs, pebble games, and homomorphism preservation results.