Exact Phase Transitions in Random Constraint Satisfaction Problems

Ke Xu, Wei Li

In this paper we propose a new type of random CSP model, called Model RB, which is a revision to the standard Model B. It is proved that phase transitions from a region where almos…