A general model and thresholds for random constraint satisfaction problems

摘要

In this paper, we study the relation among the parameters in their most general setting that define a large class of random CSP models d-k-CSP where d is the domain size and k is the length of the constraint scopes. The model d-k-CSP unifies several related models such as the model RB and the model k-CSP. We prove that the model d-k-CSP exhibits exact phase transitions if klnd increases no slower than the logarithm of the number of variables. A series of experimental studies with interesting observations are carried out to illustrate the solubility phase transition and the hardness of instances around phase transitions.