Circuit Complexity and Decompositions of Global Constraints
arXiv:0905.3757
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 ALLDIFFERENT constraint.
Proceedings of the Twenty-first International Joint Conference on Artificial Intelligence (IJCAI-09). Old file included deleted
References in corpus (3)
Cited by in corpus (14)
- A New Look at BDDs for Pseudo-Boolean Constraints
- Boolean Equi-propagation for Concise and Efficient SAT Encodings of Combinatorial Problems
- Decompositions of All Different, Global Cardinality and Related Constraints
- Towards a theory of good SAT representations
- Translation of Algorithmic Descriptions of Discrete Functions to SAT with Applications to Cryptanalysis Problems
- Trading inference effort versus size in CNF Knowledge Compilation
- A framework for good SAT translations, with applications to CNF representations of XOR constraints
- Bounds on the size of PC and URC formulas
- On the Quest for an Acyclic Graph
- Decomposition of the NVALUE constraint
- Constraint Reductions
- SAT vs CSP: a commentary
- Efficient Approximation of Well-Founded Justification and Well-Founded Domination (Corrected and Extended Version)
- Translation-based Constraint Answer Set Solving