Constraint Satisfaction Problems Solvable by Local Consistency Methods

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-Zadori [AU'07].

Keywords

• Algorithms
• Theory
• Constraint satisfaction problem
• local consistency checking