Vi visar att verktyg från kretsens komplexitet kan användas för att studera nedbrytningar av globala begränsningar. I synnerhet studerar vi nedbrytningar av globala begränsningar i konjunktiv normal form med den egenskap som enheten förökar sig på nedbrytningen upprätthåller samma nivå av konsekvens som en specialiserad förökningsalgoritm. Vi bevisar att en begränsande propagator har en polynom storlek sönderdelning om och endast om det kan beräknas av en polynom storlek monoton Booleska krets. Nedre gränser på storleken av monotona booleska kretsar översätter därmed till lägre gränser på storleken av nedbrytningar av globala begränsningar. Till exempel, vi bevisar att det inte finns någon polynom storlek nedbrytning av domänkonsistens propagator för ALLDIFERENT begränsning.
Med hjälp av en krets komplexitet lägre gräns, visade vi också att det inte finns någon polynom storlek SAT nedbrytning av ALL-DIFFERENT begränsning (och därmed av dess generaliseringar som NVALUE) på vilken enhet spridning uppnår domänkonsistens REF.
Circuit Complexity and Decompositions of Global Constraints
{'venue': 'IJCAI-2009', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}