[TopOx] Jakub Opršal: Homotopy theory in the complexity of homomorphism problems

27th of November 2025

I will talk about an emerging connection between homotopy theory and computational complexity of discrete problems. I will outline a theorem stating that contractibility is necessary for tractability (assumin P ≠ NP) in the realm of finite-template constraint satisfaction problems (CSPs).

There are many ways the CSP can be formulated. One of them is as a homomorphism problem: given two relational structures A and B, decide whether there is a homomorphism from A to B. We usually study a restricted version of this problem where B is fixed, e.g., if B is the k-clique graph K_k, the problem is the same as k-colouring of a given graph A. If B is finite (and of finite signature), such a problem is called finite-template. Famously, finite-template CSPs exhibit a P vs NP-complete dichotomy as proved independently by Bulatov and Zhuk in 2017.

The main theorem of the talk states a sufficient condition for NP-completeness in terms of the topology of ‘solution spaces’ and provides both all necessary hardness for the Bulatov–Zhuk dichotomy and also a new proof of an earlier Hell–Nešetřil dichotomy of graph homomorphism problems.