On the Scaling Window of Model RB

Zhao, Chunyan; Xu, Ke; Zheng, Zhiming

On the Scaling Window of Model RB

Authors

Zhao, Chunyan

Xu, Ke

Zheng, Zhiming

Description

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,δ)=(r_{-}(n,δ), r_{+}(n,δ))$ such that the probability of a random instance being satisfiable is greater than $1-δ$ for $r<r_{-}(n,δ)$ and is less than $δ$ for $r>r_{+}(n,δ)$. Specifically, we obtain the following result $$W(n,δ)=(r_{cr}-Θ(\frac{1}{n^{1-ε}\ln n}), \ r_{cr}+Θ(\frac{1}{n\ln n})),$$ where $0\leqε<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.