Constraint Satisfaction Problems Solvable by Local Consistency Methods

Abstrakt

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].

Klíčová slova

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