Constraint Absorption Capacity and Slack Collapse in Constraint Satisfaction Problems
Abstract
We introduce Constraint Absorption Capacity (CAC), an invariant describing the maximum constraint density that a fixed logical language and inference mechanism can absorb before additional constraints induce monotone loss of satisfiability slack. Using an entropy-style slack functional, we state an exploratory Capacity Collapse Lemma explaining sharp phase transitions and hardness peaks in random constraint satisfaction problems (CSPs), including SAT. The note is definitional and explanatory and makes no algorithmic or complexity-class claims.
Fields of Study & Subjects
Constraint Satisfaction and Optimization
Advanced Graph Theory Research
Logic
Reasoning
and Knowledge
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 7 January 2026
- Language
- EN
- Document type
- Preprint