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].
Paper
Full text
Constraint Satisfaction Problems Solvable by Local Consistency Methods
Semantic Scholar · Computer Science · 2014
Abstract
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].
References (36)
Scroll for more · 24 remaining