Tue, 4 Mar 2025, 1:25 pm MT
The Bodirsky-Pinsker conjecture is an infinite counterpart to the Feder-Vardi dichotomy conjecture for Constraint Satisfaction Problems (CSPs) with finite templates. While the latter has been confirmed independently by Bulatov and Zhuk, the former remains wide open. In this talk, we shed light on three meta-problems regarding the scope of this conjecture.
Our first result provides a significant structural simplification of this scope: we prove that the conjecture is equivalent to its restriction to templates without algebraicity, a crucial assumption in many powerful classification methods. The second result provides a simplification of algebraic nature: any algebraic condition characterizing any complexity class within the conjecture must be satisfiable by injections. In particular, this offers insight into which universal-algebraic conditions for the complexity of finite-template CSPs may be successfully lifted to the infinite case. The third result we are going to explore links the conjecture to so-called Promise Constraint Satisfaction Problems (PCSPs): using the construction from the first result, virtually every structure from the scope of the conjecture allows us to construct a sandwich structure for a non-finitely tractable finite-domain PCSP.
This is joint work with Michael Pinsker, Jakub Rydval and Christoph Spiess.