Exact Phase Transitions in Random Constraint Satisfaction Problems

Details Exact Phase Transitions in Random Constraint Satisfaction Problems Exact Phase Transitions in Random Constraint Satisfaction Problems

2000-04-16

arxiv.org/abs/cs/0004005v1

Journal of Artificial Intelligence Research, Vol 12, (2000), 93-103.

Computer Science

Artificial Intelligence

See http://www.jair.org/ for any accompanying files

Scientific paper

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 almost all problems are satisfiable to a region where almost all problems are unsatisfiable do exist for Model RB as the number of variables approaches infinity. Moreover, the critical values at which the phase transitions occur are also known exactly. By relating the hardness of Model RB to Model B, it is shown that there exist a lot of hard instances in Model RB.

Affiliated with

Also associated with

No associations

Rating

Exact Phase Transitions in Random Constraint Satisfaction Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Exact Phase Transitions in Random Constraint Satisfaction Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact Phase Transitions in Random Constraint Satisfaction Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-227938