A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems
Siu On Chan, Michael S. O. Molloy · SIAM Journal on Computing · 2013
We consider random instances of constraint satisfaction problems (CSPs) where each variable has domain size $O(1)$, each constraint is on $O(1)$ variables, and the constraints are chosen from a specified distribution. The number of constraints is $cn$, where $c$ is a constant. We prove that for every possible distribution, either the resolution complexity is almost surely polylogarithmic for sufficiently large $c$, or it is almost surely exponential for every $c>0$. We characterize the distributions of each type. To do so, we introduce a closure operation on constraint sets which yields the set of all constraints that, in some sense, appear implicitly in the random CSP.