2026-09-23T07:05:19Zhttps://api.repository.cam.ac.uk/server/oai/request

oai:www.repository.cam.ac.uk:1810/2761882025-12-19T18:09:07Zcom_1810_219481com_1810_256065col_1810_219482

Descriptive complexity of constraint problems 10.17863/CAM.23470 Wang, Pengming Dawar, Anuj 0000000340148248 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$\neq$NP, guarantees the existence of problems that are neither NP-complete, nor in P, making CSPs an exceptional class of problems. While the Feder-Vardi conjecture is proven to be true in a number of special cases, it is still open in the general setting. (Recent claims affirming the conjecture are not considered here, as they have not been peer-reviewed yet.) 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 $\Omega(n)$ levels. 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. University of Cambridge 2018-10-13 Thesis Doctoral Doctor of Philosophy (PhD) en https://www.repository.cam.ac.uk/handle/1810/276188 https://www.repository.cam.ac.uk/bitstreams/74dfacf4-8208-4d96-a318-54d7471b1aed/download 12823e96c3e4bf1f921596ff9f7ee12b https://www.repository.cam.ac.uk/bitstreams/a242f641-cd3b-4da5-8b0f-2987262b8f9f/download 87eda9de84448d1f82354d60eee3eb5f https://www.rioxx.net/licenses/all-rights-reserved/ Complexity theory Constraint satisfaction Logic Computer science Optimisation