On the Scaling Window of Model RB

Details On the Scaling Window of Model RB On the Scaling Window of Model RB

2008-01-25

arxiv.org/abs/0801.3871v1

Computer Science

Computational Complexity

Scientific paper

This paper analyzes the scaling window of a random CSP model (i.e. model RB) for which we can identify the threshold points exactly, denoted by $r_{cr}$ or $p_{cr}$. For this model, we establish the scaling window $W(n,\delta)=(r_{-}(n,\delta), r_{+}(n,\delta))$ such that the probability of a random instance being satisfiable is greater than $1-\delta$ for $rr_{+}(n,\delta)$. Specifically, we obtain the following result $$W(n,\delta)=(r_{cr}-\Theta(\frac{1}{n^{1-\epsilon}\ln n}), \ r_{cr}+\Theta(\frac{1}{n\ln n})),$$ where $0\leq\epsilon<1$ is a constant. A similar result with respect to the other parameter $p$ is also obtained. Since the instances generated by model RB have been shown to be hard at the threshold, this is the first attempt, as far as we know, to analyze the scaling window of such a model with hard instances.

Affiliated with

Also associated with

No associations

Rating

On the Scaling Window of Model RB 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 On the Scaling Window of Model RB, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Scaling Window of Model RB will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-412196