AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
Circuit Complexity and Decompositions of Global Constraints
Christian Bessiere, George Katsirelos, Nina Narodytska, Toby Walsh

Last modified: 2009-06-24

Abstract


We show that tools from circuit complexity can be used to study decompositions of global constraints. In particular, we study decompositions of global constraints into conjunctive normal form with the property that unit propagation on the decomposition enforces the same level of consistency as a specialized propagation algorithm. We prove that a constraint propagator has a a polynomial size decomposition if and only if it can be computed by a polynomial size monotone Boolean circuit. Lower bounds on the size of monotone Boolean circuits thus translate to lower bounds on the size of decompositions of global constraints. For instance, we prove that there is no polynomial sized decomposition of the domain consistency propagator for the alldiff constraint.

Full Text: PDF