BriefGPT.xyz
May, 2009
电路复杂度和全局约束的分解
Circuit Complexity and Decompositions of Global Constraints
HTML
PDF
Christian Bessiere, George Katsirelos, Nina Narodytska, Toby Walsh
TL;DR
使用电路复杂度工具研究全局约束的分解，证明约束传播器存在一个多项式大小分解，当且仅当可以通过一个多项式大小单调布尔电路计算，并证明领域一致性传播者不存在多项式大小分解。
Abstract
We show that tools from
circuit complexity
can be used to study decompositions of
global constraints
. In particular, we study decompositions of
g
→