Constraint Satisfaction Problems Solvable by Local Consistency Methods
Libor Barto, Marcin Kozik · Journal of the ACM · 2014
We prove that constraint satisfaction problems without the ability to count are solvable by the local consistency checking algorithm. This settles three (equivalent) conjectures: Feder--Vardi [SICOMP’98], Bulatov [LICS’04] and Larose--Zádori [AU’07].