The complexity of Promise Constraint Satisfaction Problems

4^th February 2025, 13:00
Andrei Krokhin
University of Durham

Abstract

The constraint satisfaction problem (CSP) can be cast as the problem of deciding the existence of a homomorphism from one relational structure (e.g. a digraph) X to another structure A. By fixing the structure A, one obtains a large family of problems, denoted CSP(A). This family includes many well-known problems including k-satisfiability and graph k-colouring. The CSP dichotomy conjecture of Feder and Vardi, that was considered to be one of the important conjectures in theoretical computer science, stated that each CSP(A) is either polynomial-time solvable or NP-complete. Following a long sustained effort by a whole research community, the Feder-Vardi conjecture was confirmed in 2017 independently by Bulatov and Zhuk. The most remarkable thing about the theory behind the resolution of the conjecture is that it gives precise structural reasons for each CSP to have this or that complexity. In this talk, I will focus mainly on the Promise CSP (PCSP), a recent significant generalisation of the standard CSP, exemplified by the approximate graph colouring problem: given a 3-colourable graph, find (say) a 1000-colouring for it. I will describe the ongoing work towards building a similar theory for PCSPs, explain the key insights and mention some important open problems.

Biography

Andrei did his PhD in Maths at Ural State University. After working for four years at Oxford and Warwick, Andrei has been for the last 20 years at the Department of Computer Science in Durham.

Additional Materials

• https://arxiv.org/abs/2208.13538