Models for random constraint satisfaction problems

© 2003 SIAM. All rights reserved.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