ABSTRACT

The phenomenon of phase transition in constraint satisfaction problems (CSPs) plays a crucial role in the field of artificial intelligence and computational complexity theory. In this paper, we propose a new random CSP called d-p-RB model, which is a generalization of RB model on domain size d and constraint tightness p. In this model, the variable domain size $d\in \left[n^{\alpha },n^{n^{\gamma }}\right]$ , and all constraints are uniformly divided into several groups with different constraint tightness p. It is proved by the second moment method that the d-p-RB model undergoes phase transition from a region where almost all instances are satisfiable to a region where almost all instances are unsatisfiable as the control parameter increases. Moreover, the threshold value at which the phase transition occurs is located exactly.

Keywords:

d-p-RB Model, Phase Transition, Domain Size, Constraint Tightness, Second Moment Method

1. Introduction

The constraint satisfaction problem (CSP in short), originated from the artificial intelligence, has become an important topic in the interdisciplinary research of computer science, mathematics and statistical physics. Many problems in the fields of artificial intelligence, computer science and automatic control can be modeled as constraint satisfaction problems. Moreover, CSPs are widely used in many practical problems such as resource allocation, pattern recognition, logistics scheduling and temporal reasoning.

In general, CSP is defined on a set of variables and a set of constraints. Each variable has a corresponding non-empty domain, the domain size of the variable can be fixed, or vary with the number of variables. Each constraint involves a randomly selected subset of variables and a corresponding compatible assignments set to specify the allowable combinations of values of the variables in this constraint. The randomly selected constraints constitute a random CSP instance. An assignment that satisfies all the constraints simultaneously is called a solution of the CSP instance. Interestingly, experimental results suggest that the probability of a random CSP instance having a solution exhibits a phase transition behavior. In a seminal paper, Cheeseman et al. showed empirically that the hardest instances of CSPs often occur around a rapid transition in solubility [1] . Since then, the phase transition phenomenon and its formation mechanism of CSPs have become one of the focuses of computational complexity theory [2] - [6] . The initial standard models for binary random CSP are A, B, C, D models [7] [8] . However, as the number of variables increases, the instances of standard models which contain flawed variables turned out to be asymptotically trivially insoluble, thus these models don’t have an asymptotic phase transition [9] . To overcome this shortcoming, some specific structures were introduced into the constraint relations such that the instances generated from these improved CSP models are arc consistent, path consistent, strongly 3-consistent or weakly 4-consistent [10] [11] [12] [13] . Although these improved models can eliminate flaws and produce nontrivial hard instances, the constraints are not generated in an easy natural way. In 2000, Xu and Li proposed RB model [14] , which is a modification of the standard model B [7] in terms of the domain size and the number of constraints. RB model is a typical random CSP model with large growing domain size which makes it overcomes the shortcoming of B model which cannot produce hard instances. Xu and Li have also shown that RB model can exhibit exact phase transition and the location of the transition point can be located precisely [14] . Moreover, Xu et al. proved theoretically and experimentally that the random instances of RB model had exponential tree-resolution complexity in the phase transition region, i.e., there are a lot of hard instances in the transition region [15] [16] , which has great practical significance for algorithm test. In 2011, Zhao and Zheng [17] introduced the finite-size scaling method in the statistical physics to analyze the threshold behaviors in RB model, and gave the upper bound of the scale window of the transition region of RB model. Inspired by the random k-SAT with moderately growing k [18] and RB model, Fan and Shen proposed a new CSP model, named k-CSP [19] . In k-CSP, the domain size is fixed while the length of constraint k is growing with the variable number n. After k-CSP, Fan et al. proposed d-k-CSP [20] , in d-k-CSP, both the domain size d and the length of constraint k are variable as two integer functions of n. It has been proved rigorously that the two CSP models do have phase transition and the exact transition point can be located exactly. In 2011, Zhao et al. proposed a message-passing algorithm, which are based on belief propagation, to solve the random CSP instances generated by RB model with large growing domain size [21] . Subsequently, Zhao et al. put forward a belief propagation algorithm [22] which is based on variable entropy and a reinforced belief propagation algorithm [23] to solve the random instances of RB model. Furthermore, they identify the connection between the structural features of the solution space and the complexity of the algorithm solving.

In this paper, we propose a new random CSP model, called d-p-RB model, which is a generalization of RB model on constraint tightness p and the variable domain size d. In RB model, the domain size $d=n^{\alpha }$ (α is a constant) is a power function of the number of variables n, and the constraint tightness p is fixed. In d-p-RB model, we uniformly divided the random constraints into several groups and diversify the domain size d as well as the constraint tightness p of the constraints in different groups. More specifically, for an instance with n variables in d-p-RB model, the domain size $d\in \left[n^{\alpha },n^{n^{\gamma }}\right]$ (α, γ are constants) is defined within a certain range rather than a single value as in RB model, for the ith group of constraints, it has its own constraint tightness $p_i$ ( $0<p_i<1$ ), which is distinct from the unchangeable p in RB model. By the second moment method, we show that the d-p-RB model can exhibit exact phase transition phenomenon under certain conditions, and the transition point can also be obtained pricey. Moreover, since both d and p are varied in d-p-RB model, it has more extensive practical significance and theoretical value.

2. Preliminaries

2.1. A CSP Instance

A CSP instance $I=\left(U,D,C\right)$ of d-p-RB model is defined as follows:

1) $U=\left\{u_1,u_2,\cdots ,u_n\right\}$ is a set of n variables.

2) $D=\left\{D_1,D_2,\cdots ,D_n\right\}$ is a domain set. Each variable $u_i$ ( $i=1,2,\cdots ,n$ ) takes values from $D_i$ , whose size $\left|D_i\right|=d\in \left[n^{\alpha },n^{n^{\lambda }}\right]$ , where α and γ are constants.

3) $C=\left\{C_1,C_2,\cdots ,C_t\right\}$ is a set of constraints, and each constraint $C_i$ is a pair ( $S_i,R_i$ ), where $S_i\text{=}\left\{s_{i_1},s_{i_2},\cdots ,s_{i_k}\right\}$ (k is the length of the constraint) is a subset of U, and $R_i\subseteq D_{i_1}\times D_{i_2}\times \cdots \times D_{i_k}$ is a compatible assignments set.

A constraint $C_i$ is satisfied if the k-tuple of values assigned to variables in $S_i$ is contained in $R_i$ . A solution of a CSP instance is an assignment to all the variables that satisfies all constraints.

2.2. d-p-RB Model

A random CSP instance in d-p-RB model is generated in the following two steps:

Step 1. We select with repetition l groups of constraints. For each group, there are $t/l$ constraints with each contains k variables, which are randomly select from u, and distinct from each other.

Step 2. For each group of constraints, we uniformly select at random without repetition $p_i{d}^k$ ( $0<p_i<1$ is the constraint tightness) compatible assignments to form the compatible assignments set $R_i$ ( $i=1,2,\cdots ,l$ ).

3. Main Result

We let $t=rn\ln d$ , where r is a constant control parameter, which determines how many constraints are in a CSP instance. Let $p=\min \left\{p_1,p_2,\cdots ,p_l\right\}$ , where $p_i$ ( $i=1,2,\cdots ,l$ ) determines how restrictive the constraints are. Let $\mathrm{Pr}\left(sat\right)$ denote the probability of a random d-p-RB instance being satisfiable, then we have the following theorem.

Theorem Let $r_m=-\frac{l}{{\displaystyle \sum _{i=1}^l\ln p_i}}$ ( $0<p_i<1$ ), if the constants k, p, α, γ satisfy the relations $\alpha >\frac{\gamma +1}{k-1}$ , $k\ge \max \left\{\frac{1}{p},\gamma +2\right\}$ then

$\underset{n\to \infty }{\lim }\mathrm{Pr}\left(sat\right)=\{\begin{array}{c}0\\ 1\end{array}\begin{array}{c}\text{when}r>r_m\\ \text{when}r<r_m\end{array}\begin{array}{c}(1)\\ (2)\end{array}$

The theorem shows that, when the number of variables n is sufficiently large, there exists a sudden shift in $r_m$ .

4. Proof of the Theorem

Let N denote the number of solutions of a random CSP instance I. The expectation and the second moment of N is denoted by $E\left(N\right)$ and $E\left(N^2\right)$ . When $r>r_m$ , we consider the Markov inequality $\mathrm{Pr}\left(sat\right)\le E\left(N\right)$ . When $r<r_m$ , by

the second moment method, we estimate the upper bound of $\frac{E\left(N^2\right)}{E^2\left(N\right)}$ , and then by the Cauchy inequality $\mathrm{Pr}\left(sat\right)\ge \frac{E^2\left(N\right)}{E\left(N^2\right)}$ , we finally attain our goal. Now we demonstrate the two cases respectively.

4.1. Proof of r > r_m

Since the constraints are generated independently in d-p-RB model, the expected number of solutions $E\left(N\right)$ is given by

$\begin{array}{c}E\left(N\right)=d^n{\left(p_1{p}_2\cdots p_l\right)}^{\frac{t}{l}}\\ =\exp \left(n\ln d+\frac{r}{l}n\ln d{\displaystyle \sum _{i=1}^l\ln p_i}\right)\\ =\exp \left[n\ln d\left(1+\frac{r}{l}{\displaystyle \sum _{i=1}^l\ln p_i}\right)\right]\end{array}$ . (3)

Since $r>r_m$ , we have

$1+\frac{r}{l}{\displaystyle \sum _{i=1}^l\ln p_i}<0$ , (4)

thus

$\underset{n\to \infty }{\lim }E\left(N\right)=0$ . (5)

Then using the Markov inequality $\mathrm{Pr}\left(sat\right)\le E\left(N\right)$ , by (5), it’s not hard to have

$\underset{n\to \infty }{\lim }\mathrm{Pr}\left(Sat\right)=0$ . (6)

4.2. Proof of r < r_m

Definition 1 (The assignment pair) Suppose that the assignment pair $\langle t_i,t_j\rangle$ is an ordered pair, where $t_i=\left(a_{i1},a_{i2},\cdots ,a_{in}\right)$ , $t_j=\left(a_{j1},a_{j2},\cdots ,a_{jn}\right)$ , and $a_{ih},a_{jh}\in D_h$ ( $h=1,2,\cdots ,n$ ). An assignment pair $\langle t_i,t_j\rangle$ satisfies a CSP instance if and only if both $t_i$ and $t_j$ satisfy the instance.

Definition 2 (The similarity number) Define a function as follows

$Sam\left(a_{ih},a_{jh}\right)=\{\begin{array}{l}1a_{ih}=a_{jh}\\ 0a_{ih}\ne a_{jh}\end{array}$

Assume $m={\displaystyle \sum _{h=1}^{n}sam\left(a_{ih},a_{jh}\right)}$ , thus the assignment pair $\langle t_i,t_j\rangle$ has m

identical assignments, i.e. the similarity number of $\langle t_i,t_j\rangle$ is m. It is obvious that $0\le m\le n$ .

Next, we use the second moment method to complete the proof.

Assume that $P\left(\langle t_i,t_j\rangle \right)$ represents the probability that $t_i$ and $t_j$ satisfy the instant I simultaneously. We analyse this probability in the following way:

Since there are m identical assignments in $t_i$ and $t_j$ , for each constraint, we have the following two cases:

1) The assignments of k variables that the constraint restricts are all same in $t_i$ and $t_j$ , in this case, the probability of $\langle t_i,t_j\rangle$ satisfying the constraint is

$\frac{\left({}_{p_i{d}^k-1}^{d^k-1}\right)}{\left({}_{p_i{d}^k}^{d^k}\right)}=p_i$ , and for a random constraint, the probability of such a situation is $\frac{\left(\begin{array}{c}m\\ k\end{array}\right)}{\left(\begin{array}{c}n\\ k\end{array}\right)}$ .

2) Otherwise, the probability of $\langle t_i,t_j\rangle$ satisfying the constraint is

$\frac{\left({}_{p_i{d}^k-2}^{d^k-2}\right)}{\left({}_{p_i{d}^k}^{d^k}\right)}=p_i\frac{p_i{d}^k-1}{d^k-1}$ , and the probability that $\langle t_i,t_j\rangle$ falls into such a situation is $1-\frac{\left(\begin{array}{c}m\\ k\end{array}\right)}{\left(\begin{array}{c}n\\ k\end{array}\right)}$ .

Let

${\sigma }_{m,n}=\frac{\left(\begin{array}{c}m\\ k\end{array}\right)}{\left(\begin{array}{c}n\\ k\end{array}\right)},s=\frac{m}{n}.$ (7)

Since

${\sigma }_{m,n}=\frac{\left(\begin{array}{c}m\\ k\end{array}\right)}{\left(\begin{array}{c}n\\ k\end{array}\right)}=\frac{m\left(m-1\right)\cdots \left(m-k+1\right)}{n\left(n-1\right)\cdots \left(n-k+1\right)}\le {\left(\frac{m}{n}\right)}^k$ (8)

we have

${\sigma }_{m,n}\le s^k.$ (9)

Since the constraints are generated independently, the assignment pair $\langle t_i,t_j\rangle$ satisfying all the constraints in random instance i is

$\begin{array}{c}P\left(\langle t_i,t_j\rangle \right)={\displaystyle \prod _{i=1}^l{\left[p_i{\sigma }_{m,n}+p_i\frac{p_i{d}^k-1}{d^k-1}\left(1-{\sigma }_{m,n}\right)\right]}^{\frac{t}{l}}}\\ \le {\displaystyle \prod _{i=1}^l{p}_i^{\frac{t}{l}}{\left[{\sigma }_{S,n}+p_i\left(1-{\sigma }_{S,n}\right)\right]}^{\frac{t}{l}}}\\ \le {\displaystyle \prod _{\text{i=}1}^l{p}_i^{\frac{t}{l}}{\left[p_i+\left(1-p_i\right)s^k\right]}^{\frac{t}{l}}}\\ \le {\displaystyle \prod _{i=1}^l{p}_i^{\frac{2t}{l}}{\left(1+\frac{1-p_i}{p_i}{s}^k\right)}^{\frac{t}{l}}}.\end{array}$ (10)

Let $A_m$ be the set of assignment pairs whose similarity number is m, $\left|A_m\right|$ be the cardinality of $A_m$ , then we have

$\left|A_m\right|=d^n\left(\begin{array}{c}n\\ m\end{array}\right){\left(d-1\right)}^{n-m}=d^{2n}\left(\begin{array}{c}n\\ m\end{array}\right){\left(1-\frac{1}{d}\right)}^{n-m}{\left(\frac{1}{d}\right)}^m$ . (11)

Thus by (10) and (11), the second order moment of the number of solutions of the random instance of d-p-RB model is

$\begin{array}{c}E\left(N^2\right)={\displaystyle \sum _{m=0}^n\left|A_m\right|}P\left(\langle t_i,t_j\rangle \right)\\ \le {\displaystyle \sum _{m=0}^n{d}^{2n}\left(\begin{array}{c}n\\ m\end{array}\right){\left(1-\frac{1}{d}\right)}^{n-m}{\left(\frac{1}{d}\right)}^m{\displaystyle \prod _{i=1}^l{p}_i^{\frac{2t}{l}}{\left(1+\frac{1-p_i}{p_i}{s}^k\right)}^t}}\\ \text{=}{E}^2\left(N\right){\displaystyle \sum _{m=0}^n\left(\begin{array}{c}n\\ m\end{array}\right){\left(1-\frac{1}{d}\right)}^{n-m}{\left(\frac{1}{d}\right)}^m{\displaystyle \prod _{i=1}^l{\left(1+\frac{1-p_i}{p_i}{s}^k\right)}^{\frac{t}{l}}}}\\ =E^2\left(N\right){\displaystyle \sum _{0\le s\le 1}B\left(s\right)W\left(s\right)},\end{array}$ (12)

where

$B\left(s\right)=\left({}_{ns}^n\right){\left(1-\frac{1}{d}\right)}^{n-ns}{\left(\frac{1}{d}\right)}^{ns}$ (13)

$W\left(s\right)={\displaystyle \prod _{i=1}^l{\left(1+\frac{1-p_i}{p_i}{s}^k\right)}^{\frac{t}{l}}}$ , (14)

i.e.,

$\frac{E\left(N^2\right)}{E^2\left(N\right)}\le {\displaystyle \sum _{0\le s\le 1}B\left(s\right)W}\left(s\right)$ . (15)

Considering that $0\le s\le 1$ , in order to evaluate the upper bound of the above Inequality (15), we divide the interval [0,1] into three parts: $\left[0,s_1\right]$ , $\left[s_1,s_2\right]$ ,

$\left[s_2,1\right]$ , where $s_1=\frac{1}{n^{\beta }}$ , $s_2=\frac{1}{n^{\frac{\gamma +1}{k-1}}}$ , here β and γ satisfy $\frac{\gamma +1}{k-1}<\beta <\min \left\{1,\alpha \right\}$ .

1) For $s\in \left[0,s_1\right]$ , let $s_1=\frac{1}{n^{\beta }}$ , where $\frac{\gamma +1}{k-1}<\beta <\min \left\{1,\alpha \right\}$ , recalling that

$t=rn\ln d$ , $d\in \left[n^{\alpha },n^{n^{\gamma }}\right]$ , and $p=\min \left\{p_1,p_2,\cdots ,p_l\right\}$ we have

$\begin{array}{c}W\left(s\right)={\displaystyle \prod _{i=1}^l{\left(1+\frac{1-p_i}{p_i}{s}^k\right)}^{\frac{rn\ln d}{l}}}\\ \le {\left(1+\frac{1-p}{p}{s}^k\right)}^{rn\ln d}\\ \le \exp \left[rn\ln d\ln \left(1+\frac{1-p}{p}{s}^k\right)\right]\\ \le \exp \left(rn\ln d\cdot \frac{1-p}{p}\cdot s^k\right)\\ \le \exp \left[\frac{r\left(1-p\right)}{p}{n}^{\gamma +1-\beta k}\ln n\right].\end{array}$ (16)

Since $\beta >\frac{\gamma +1}{k-1}>\frac{\gamma +1}{k}$ , $\gamma +1-\beta k<0$ , we get

$\underset{n\to \infty }{\lim }W\left(s\right)=1$ . (17)

Then it is not hard to obtain that

${\displaystyle \sum _{0\le s\le s_1}B\left(s\right)}W\left(s\right)\le {\displaystyle \sum _{0\le s\le s_1}B\left(s\right)}\le {\displaystyle \sum _{0\le s\le 1}B\left(s\right)}=1$ . (18)

2) For $s\in \left[s_1,s_2\right]$ , let $s_2=\frac{1}{n^{\frac{\gamma +1}{k-1}}}$ , $f\left(s\right)=-s\ln s-\left(1-s\right)\ln \left(1-s\right)$ , by the Stirling’s formula $n!={\left(\frac{n}{\text{e}}\right)}^n\sqrt{2\text{π}n}{\text{e}}^{\frac{\epsilon }{12n}}$ , where $\left|\epsilon \right|<1$ , it’s not hard to see

$\left(\begin{array}{c}n\\ ns\end{array}\right)<{\text{e}}^{nh\left(s\right)}$ . (19)

Since

$B\left(s\right)W\left(s\right)\le \left({}_{ns}^n\right){\left(1-\frac{1}{d}\right)}^{n-ns}{\left(\frac{1}{d}\right)}^{ns}{\left(1+\frac{1-p}{p}{s}^k\right)}^{rn\ln d}$ (20)

we get

$\begin{array}{c}\ln B\left(s\right)W\left(s\right)\le nf\left(s\right)+\left(n-ns\right)\ln \left(1-\frac{1}{d}\right)-ns\ln d+\frac{r}{l}n\ln d\ln \left(1+\frac{1-p}{p}{s}^k\right)\\ \le n\left[f\left(s\right)-s\ln d+\frac{r\left(1-p\right)}{lp}\cdot \ln d\cdot s^k\right]\\ \le ns\left[-\ln s-\frac{1-s}{s}\ln \left(1-s\right)-\alpha \ln n+\frac{r\left(1-p\right)}{lp}\cdot n^{\gamma }\cdot \ln n\cdot s^{k-1}\right].\end{array}$ (21)

For $s\in \left[s_1,s_2\right]$ , we have

$\begin{array}{c}\ln B\left(s\right)W\left(s\right)\le ns\left[\beta \ln n+1-\alpha \ln n+\frac{r\left(1-p\right)}{lp}\cdot n^{\gamma }\cdot \ln n\cdot {\left(\frac{1}{n^{\frac{\gamma +1}{k-1}}}\right)}^{k-1}\right]\\ \text{=}ns\ln n\left[\beta -\alpha +\frac{1}{\ln n}+\frac{r\left(1-p\right)}{lp}\cdot \frac{1}{n}\right]\\ \le n^{1-\beta }\ln n\left[\beta -\alpha +o\left(\frac{1}{\ln n}\right)\right].\end{array}$ (22)

Since $\beta <\min \left\{1,\alpha \right\}$ , we have

$\underset{n\to \infty }{\lim }\ln B\left(s\right)W\left(s\right)=-\infty$ , (23)

hence

$\begin{array}{c}{\displaystyle \sum _{s_1\le s\le s_2}B\left(s\right)W\left(s\right)}\le nB\left(s\right)W\left(s\right)\\ \le n\exp \left[n^{1-\beta }\ln n\left(\beta -\alpha +o\left(\frac{1}{\ln n}\right)\right)\right]\\ =n^{n^{1-\beta }\left(\beta -\alpha +o\left(\frac{1}{\ln n}\right)\right)+1}\to 0\left(n\to \infty \right).\end{array}$ (24)

Thus, for arbitrary small ε, there exists an integer $N_1>0$ , such that

${\displaystyle \sum _{s_1\le s\le s_2}B\left(s\right)}W\left(s\right)<\frac{\epsilon }{2}$ . (25)

3) For $s\in \left[s_2,1\right]$ we have

$B\left(s\right)W\left(s\right)=\left({}_{ns}^n\right){\left(1-\frac{1}{d}\right)}^{n-ns}{\left(\frac{1}{d}\right)}^{ns}{\displaystyle \prod _{i=1}^l{\left(1+\frac{1-p_i}{p_i}{s}^k\right)}^{\frac{rn\ln d}{l}}}$ (26)

Then

$\begin{array}{c}\ln B\left(s\right)W\left(s\right)\le nf\left(s\right)-ns\ln d+\frac{r}{l}n\ln d{\displaystyle \sum _{i=1}^l\ln \left(1+\frac{1-p_i}{p_i}{s}^k\right)}\\ =n\left[f\left(s\right)+\ln d\left(-s+\frac{r}{l}{\displaystyle \sum _{i=1}^l\ln \left(1+\frac{1-p_i}{p_i}{s}^k\right)}\right)\right].\end{array}$ (27)

Let $g\left(s\right)=\frac{r}{l}{\displaystyle \sum _{i=1}^l\ln \left(1+\frac{1-p_i}{p_i}{s}^k\right)}-s$ , differentiating $g\left(s\right)$ with respect to s, we get

$g^{\prime }\left(s\right)=\frac{r}{l}{\displaystyle \sum _{i=1}^l\frac{k\left(1-p_i\right)s^{k-1}}{p_i+\left(1-p_i\right)s^k}}-1$ , (28)

and then

$g^{″}\left(s\right)=\frac{r}{l}{\displaystyle \sum _{i=1}^l\frac{k\left(1-p_i\right)s^{k-2}\left[\left(k-1\right)p_i+\left(1-p_i\right)s^k\right]}{{\left[p_i+\left(1-p_i\right)s^k\right]}^2}}$ . (29)

By the condition $k\ge \frac{1}{p}$ , we have $g^{″}\left(s\right)\ge 0$ , which implies that $g\left(s\right)$ is convex for $s\in \left[0,1\right]$ . Note that $g\left(0\right)=0$ and $g\left(1\right)=-\frac{r}{l}{\displaystyle \sum _{i=1}^l\ln p_i}-1<0$ for $r<r_m=-l/{\displaystyle \sum _{i=1}^l\ln p_i}$ , therefore we get $g\left(s\right)<0$ for $s\in \left[s_2,1\right]$ . Let ${\max }_{s\in \left[s_2,1\right]}g\left(s\right)=-M$ , where $M>0$ is a constant.

For $f\left(s\right)=-s\ln s-\left(1-s\right)\ln \left(1-s\right)$ , similarly we have

$f^{\prime }\left(s\right)=-\ln s+\ln \left(1-s\right)$ (30)

$f^{″}\left(s\right)=-\frac{1}{s\left(1-s\right)}<0$ . (31)

So $f\left(s\right)$ is concave and has the maximum value $\ln 2$ at $s=\frac{1}{2}$ . Thus we have

$\ln B\left(s\right)W\left(s\right)\le n\left[f\left(s\right)+\ln d\cdot g\left(s\right)\right]\le n\left(\ln 2-M\ln d\right).$ (32)

So we get

${\displaystyle \sum _{s_2\le s\le 1}B\left(s\right)W\left(s\right)}\le nB\left(s\right)W\left(s\right)\le n\exp \left(n\ln 2-M\ln d\right)\le 2^n{n}^{-\alpha Mn+1}$ , (33)

hence

$\underset{n\to \infty }{\lim }{\displaystyle \sum _{s_2\le s\le 1}B\left(s\right)W\left(s\right)}=0$ , (34)

i.e., for $s\in \left[s_2,1\right]$ , there exists an integer $N_2>0$ , such that

${\displaystyle \sum _{s_2\le s\le 1}B\left(s\right)W\left(s\right)}<\frac{\epsilon }{2}$ . (35)

Summarizing the above, from (18), (25), (35), letting $N=\max \left\{N_1,N_2\right\}$ , we obtain

${\displaystyle \sum _{0\le s\le 1}B\left(s\right)W\left(s\right)}<1+\epsilon$ . (36)

Thus we have

$\frac{E\left(N^2\right)}{E^2\left(N\right)}\le 1\text{+}\epsilon$ , (37)

then by the Cauchy inequality $\mathrm{Pr}\left(sat\right)\ge \frac{E^2\left(N\right)}{E\left(N^2\right)}$ , we have

$\frac{1}{1+\epsilon }\le \mathrm{Pr}\left(sat\right)\le 1$ , (38)

then we get

$\underset{n\to \infty }{\lim }\mathrm{Pr}\left(sat\right)=1$ . （39）

Thus the theorem is proved.

So far we have demonstrated the satisfiability phase transition in theory. From the proof of the theorem, it can be seen that when the control parameter r is less than the transition point $r_m$ , the probability of a CSP instance being satisfied tends to 1, while the control parameter r is greater than the transition point $r_m$ , the probability tends to 0. Thus there exists a sharp threshold in the CSP instances generated by d-p-RB model.

5. Conclusion

In this paper, we propose a new CSP model d-p-RB. Compared with RB model, we diversify the constraint tightness p and broaden the domain size d. By the method of second moment, we proved that there indeed exist satisfiability phase transition phenomenon and the transition point can also be located exactly.

Cite this paper

Liu, Y.N. (2017) Sharp Thresholds for a Random Constraint Satisfaction Problem. Open Journal of Applied Sciences, 7, 574-584. https://doi.org/10.4236/ojapps.2017.710041

References