Models and thresholds for random constraint satisfaction problems

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 exhibit thresholds for satisfiability in the sense that the limiting probability of satisfiability changes significantly as the number of constraints increases. We also discuss models which exhibit sharp thresholds in the sense that the limiting probability jumps from 0 to 1 suddenly.

Authors

• Michael Molloy 0001

Keywords

• sharp thresholds