The Resolution Complexity of Random Constraint Satisfaction Problems
Michael S. O. Molloy, Mohammad R. Salavatipour · SIAM Journal on Computing · 2007
We consider random instances of constraint satisfaction problems where each variable has domain size d and each constraint contains t restrictions on k variables. For each $(d,k,t)$ we determine whether the resolution complexity is a.s. constant, polynomial, or exponential in the number of variables. For a particular range of $(d,k,t)$, we determine a sharp threshold for resolution complexity where the resolution complexity drops from a.s. exponential to a.s. polynomial when the clause density passes a specific value.