Models for Random Constraint Satisfaction Problems
Michael S. O. Molloy · SIAM Journal on Computing · 2003
We introduce a class of models for random constraint satisfaction problems. This class includes and generalizes many previously studied models. We characterize those models from our class which are asymptotically interesting in the sense that the limiting probability of satisfiability changes significantly as the number of constraints increases. We also discuss models which exhibit a sharp threshold for satisfiability in the sense that the limiting probability jumps from 0 to 1 suddenly as the number of constraints increases.