Homotopy Theory in the Complexity of Homomorphism Problems

Explore an emerging connection between homotopy theory and computational complexity of discrete problems in this conference talk. Learn about a groundbreaking theorem demonstrating that contractibility is necessary for tractability (assuming P ≠ NP) within finite-template constraint satisfaction problems (CSPs). Discover how CSPs can be formulated as homomorphism problems, where you decide whether there exists a homomorphism from one relational structure to another, with applications ranging from graph k-coloring to broader computational challenges. Examine the famous P vs NP-complete dichotomy for finite-template CSPs as independently proved by Bulatov and Zhuk in 2017. Understand how the main theorem provides a sufficient condition for NP-completeness through the topology of solution spaces, offering both necessary hardness conditions for the Bulatov–Zhuk dichotomy and a novel proof of the earlier Hell–Nešetřil dichotomy for graph homomorphism problems.