ay="inline" xmlns="http://www.w3.org/1998/Math/MathML"> C i is a pair ( S i , R i ), where S i = { s i 1 , s i 2 , , s i k } (k is the length of the constraint) is a subset of U, and R i D i 1 × D i 2 × × 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 , , l ).

3. Main Result

We let t = r n ln d , where r is a constant control parameter, which determines how many constraints are in a CSP instance. Let p = min { p 1 , p 2 , , p l } , where p i ( i = 1 , 2 , , l ) determines how restrictive the constraints are. Let Pr ( s a t ) denote the probability of a random d-p-RB instance being satisfiable, then we have the following theorem.

Theorem Let r m = l i = 1 l ln p i ( 0 < p i < 1 ), if the constants k, p, α, γ satisfy the relations α > γ + 1 k 1 , k max { 1 p , γ + 2 } then

lim n Pr ( s a t ) = { 0 1 when r > r m when r < r m ( 1 ) (2)

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 ( N ) and E ( N 2 ) . When r > r m , we consider the Markov inequality Pr ( s a t ) E ( N ) . When r < r m , by

the second moment method, we estimate the upper bound of E ( N 2 ) E 2 ( N ) , and then by the Cauchy inequality Pr ( s a t ) E 2 ( N ) E ( N 2 ) , we finally attain our goal. Now we demonstrate the two cases respectively.

4.1. Proof of r > rm

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

E ( N ) = d n ( p 1 p 2 p l ) t l = exp ( n ln d + r l n ln d i = 1 l ln p i ) = exp [ n ln d ( 1 + r l i = 1 l ln p i ) ] . (3)

Since r > r m , we have

1 + r l i = 1 l ln p i < 0 , (4)

thus

lim n E ( N ) = 0 . (5)

Then using the Markov inequality Pr ( s a t ) E ( N ) , by (5), it’s not hard to have

lim n Pr ( S a t ) = 0 . (6)

4.2. Proof of r < rm

Definition 1 (The assignment pair) Suppose that the assignment pair t i , t j is an ordered pair, where t i = ( a i 1 , a i 2 , , a i n ) , t j = ( a j 1 , a j 2 , , a j n ) , and a i h , a j h D h ( h = 1 , 2 , , n ). An assignment pair t i , t j 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

S a m ( a i h , a j h ) = { 1 a i h = a j h 0 a i h a j h

Assume m = h = 1 n s a m ( a i h , a j h ) , thus the assignment pair t i , t j has m

identical assignments, i.e. the similarity number of t i , t j is m. It is obvious that 0 m n .

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

Assume that P ( t i , t j ) 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 t i , t j satisfying the constraint is

( p i d k 1 d k 1 ) ( p i d k d k ) = p i , and for a random constraint, the probability of such a situation is ( m k ) ( n k ) .

2) Otherwise, the probability of t i , t j satisfying the constraint is

( p i d k 2 d k 2 ) ( p i d k d k ) = p i p i d k 1 d k 1 , and the probability that t i , t j falls into such a situation is 1 ( m k ) ( n k ) .

Let

σ m , n = ( m k ) ( n k ) , s = m n . (7)

Since

σ m , n = ( m k ) ( n k ) = m ( m 1 ) ( m k + 1 ) n ( n 1 ) ( n k + 1 ) ( m n ) k (8)

we have

σ m , n s k . (9)

Since the constraints are generated independently, the assignment pair t i , t j satisfying all the constraints in random instance i is

P ( t i , t j ) = i = 1 l [ p i σ m , n + p i p i d k 1 d k 1 ( 1 σ m , n ) ] t l i = 1 l p i t l [ σ S , n + p i ( 1 σ S , n ) ] t l i= 1 l p i t l [ p i + ( 1 p i ) s k ] t l i = 1 l p i 2 t l ( 1 + 1 p i p i s k ) t l . (10)

Let A m be the set of assignment pairs whose similarity number is m, | A m | be the cardinality of A m , then we have

| A m | = d n ( n m ) ( d 1 ) n m = d 2 n ( n m ) ( 1 1 d ) n m ( 1 d ) 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

E ( N 2 ) = m = 0 n | A m | P ( t i , t j ) m = 0 n d 2 n ( n m ) ( 1 1 d ) n m ( 1 d ) m i = 1 l p i 2 t l ( 1 + 1 p i p i s k ) t = E 2 ( N ) m = 0 n ( n m ) ( 1 1 d ) n m ( 1 d ) m i = 1 l ( 1 + 1 p i p i s k ) t l = E 2 ( N ) 0 s 1 B ( s ) W ( s ) , (12)

where

B ( s ) = ( n s n ) ( 1 1 d ) n n s ( 1 d ) n s (13)

W ( s ) = i = 1 l ( 1 + 1 p i p i s k ) t l , (14)

i.e.,

E ( N 2 ) E 2 ( N ) 0 s 1 B ( s ) W ( s ) . (15)

Considering that 0 s 1 , in order to evaluate the upper bound of the above Inequality (15), we divide the interval [0,1] into three parts: [ 0 , s 1 ] , [ s 1 , s 2 ] ,

[ s 2 , 1 ] , where s 1 = 1 n β , s 2 = 1 n γ + 1 k 1 , here β and γ satisfy γ + 1 k 1 < β < min { 1 , α } .

1) For s [ 0 , s 1 ] , let s 1 = 1 n β , where γ + 1 k 1 < β < min { 1 , α } , recalling that

t = r n ln d , d [ n α , n n γ ] , and p = min { p 1 , p 2 , , p l } we have

W ( s ) = i = 1 l ( 1 + 1 p i p i s k ) r n ln d l ( 1 + 1 p p s k ) r n ln d exp [ r n ln d ln ( 1 + 1 p p s k ) ] exp ( r n ln d 1 p p s k ) exp [ r ( 1 p ) p n γ + 1 β k ln n ] . (16)

Since β > γ + 1 k 1 > γ + 1 k , γ + 1 β k < 0 , we get

lim n W ( s ) = 1 . (17)

Then it is not hard to obtain that

0 s s 1 B ( s ) W ( s ) 0 s s 1 B ( s ) 0 s 1 B ( s ) = 1 . (18)

2) For s [ s 1 , s 2 ] , let s 2 = 1 n γ + 1 k 1 , f ( s ) = s ln s ( 1 s ) ln ( 1 s ) , by the Stirling’s formula n ! = ( n e ) n 2 π n e ε 12 n , where | ε | < 1 , it’s not hard to see

( n n s ) < e n h ( s ) . (19)

Since

B ( s ) W ( s ) ( n s n ) ( 1 1 d ) n n s ( 1 d ) n s ( 1 + 1 p p s k ) r n ln d (20)

we get

ln B ( s ) W ( s ) n f ( s ) + ( n n s ) ln ( 1 1 d ) n s ln d + r l n ln d ln ( 1 + 1 p p s k ) n [ f ( s ) s ln d + r ( 1 p ) l p ln d s k ] n s [ ln s 1 s s ln ( 1 s ) α ln n + r ( 1 p ) l p n γ ln n s k 1 ] . (21)

For s [ s 1 , s 2 ] , we have

ln B ( s ) W ( s ) n s [ β ln n + 1 α ln n + r ( 1 p ) l p n γ ln n ( 1 n γ + 1 k 1 ) k 1 ] = n s ln n [ β α + 1 ln n + r ( 1 p ) l p 1 n ] n 1 β ln n [ β α + o ( 1 ln n ) ] . (22)

Since β < min { 1 , α } , we have

lim n ln B ( s ) W ( s ) = , (23)

hence

s 1 s s 2 B ( s ) W ( s ) n B ( s ) W ( s ) n exp [ n 1 β ln n ( β α + o ( 1 ln n ) ) ] = n n 1 β ( β α + o ( 1 ln n ) ) + 1 0 ( n ) . (24)

Thus, for arbitrary small ε, there exists an integer N 1 > 0 , such that

s 1 s s 2 B ( s ) W ( s ) < ε 2 . (25)

3) For s [ s 2 , 1 ] we have

B ( s ) W ( s ) = ( n s n ) ( 1 1 d ) n n s ( 1 d ) n s i = 1 l ( 1 + 1 p i p i s k ) r n ln d l (26)

Then

ln B ( s ) W ( s ) n f ( s ) n s ln d + r l n ln d i = 1 l ln ( 1 + 1 p i p i s k ) = n [ f ( s ) + ln d ( s + r l i = 1 l ln ( 1 + 1 p i p i s k ) ) ] . (27)

Let g ( s ) = r l i = 1 l ln ( 1 + 1 p i p i s k ) s , differentiating g ( s ) with respect to s, we get

g ( s ) = r l i = 1 l k ( 1 p i ) s k 1 p i + ( 1 p i ) s k 1 , (28)

and then

g ( s ) = r l i = 1 l k ( 1 p i ) s k 2 [ ( k 1 ) p i + ( 1 p i ) s k ] [ p i + ( 1 p i ) s k ] 2 . (29)

By the condition k 1 p , we have g ( s ) 0 , which implies that g ( s ) is convex for s [ 0 , 1 ] . Note that g ( 0 ) = 0 and g ( 1 ) = r l i = 1 l ln p i 1 < 0 for r < r m = l / i = 1 l ln p i , therefore we get g ( s ) < 0 for s [ s 2 , 1 ] . Let max s [ s 2 , 1 ] g ( s ) = M , where M > 0 is a constant.

For f ( s ) = s ln s ( 1 s ) ln ( 1 s ) , similarly we have

f ( s ) = ln s + ln ( 1 s ) (30)

f ( s ) = 1 s ( 1 s ) < 0 . (31)

So f ( s ) is concave and has the maximum value ln 2 at s = 1 2 . Thus we have

ln B ( s ) W ( s ) n [ f ( s ) + ln d g ( s ) ] n ( ln 2 M ln d ) . (32)

So we get

s 2 s 1 B ( s ) W ( s ) n B ( s ) W ( s ) n exp ( n ln 2 M ln d ) 2 n n α M n + 1 , (33)

hence

lim n s 2 s 1 B ( s ) W ( s ) = 0 , (34)

i.e., for s [ s 2 , 1 ] , there exists an integer N 2 > 0 , such that

s 2 s 1 B ( s ) W ( s ) < ε 2 . (35)

Summarizing the above, from (18), (25), (35), letting N = max { N 1 , N 2 } , we obtain

0 s 1 B ( s ) W ( s ) < 1 + ε . (36)

Thus we have

E ( N 2 ) E 2 ( N ) 1 + ε , (37)

then by the Cauchy inequality Pr ( s a t ) E 2 ( N ) E ( N 2 ) , we have

1 1 + ε Pr ( s a t ) 1 , (38)

then we get

lim n Pr ( s a t ) = 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. (2017) Sharp Thresholds for a Random Constraint Satisfaction Problem. Open Journal of Applied Sciences, 7, 574-584. doi: 10.4236/ojapps.2017.710041.
References
[1]   Cheesema, P., Kanefsky, B. and Taylor, W.M. (1991) Where the Really Hard Problems Are. Proceedings of the 12th International Joint Conference on Artificial Intelligence, Sydney, 24-30 August 1991, 331-337.

[2]   Prosser, P. (1996) An Empirical Study of Phase Transitions in Binary Constraint Satis-faction Problems. Artificial Intelligence, 81, 81-109.
https://doi.org/10.1016/0004-3702(95)00048-8

[3]   Friedgut, E. and Bourgain, J. (1999) Sharp Thresholds of Graph Properties, and the k-SAT Problem. Journal of the American Mathematical Society, 12, 1017-1054.
https://doi.org/10.1090/S0894-0347-99-00305-7

[4]   Smith, B.M. (2001) Constructing an Asymptotic Phase Transition in Random Binary Constraint Satisfaction Problems. Theoretical Computer Science, 265, 265-283.
https://doi.org/10.1016/S0304-3975(01)00166-9

[5]   Friedgut, E. (2005) Hunting for Sharp Thresholds. Random Structures and Algorithms, 26, 37-51. https://doi.org/10.1002/rsa.20042

[6]   Frieze, A.M. and Molloy, M. (2006) The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems. Random Structures and Algorithms, 28, 323-339.
https://doi.org/10.1002/rsa.20118

[7]   Smith, B.M. and Dyer, M.E. (1996) Locating the Phase Transition in Binary Constraint Satisfaction Problems. Artificial Intelligence, 81, 155-181.
https://doi.org/10.1016/0004-3702(95)00052-6

[8]   Gent, I., Macintyre, E., Prosser, P. and Smith, B. (2001) Random Constraint Satisfaction: Flaws and Structure. Constraints, 6, 345-372.
https://doi.org/10.1023/A:1011454308633

[9]   Achlioptas, D., Kirousis, L., Kranakis, E., Krizanc, D., Molloy, M. and Stamatiou, Y. (1997) Random Constraint Satisfaction: A More Accurate Picture. Proceedings of the Third International Conference on Principles and Practice of Constraint Programming, Austria, 29 October-1 November 1997, 107-120.
https://doi.org/10.1007/BFb0017433

[10]   Molloy, M. (2003) Models for Random Constraint Satisfaction Problems. SIAM Journal of Computing, 32, 935-949.
https://doi.org/10.1137/S0097539700368667

[11]   Yong, G. and Joseph, C. (2004) Consistency and Random Constraint Satisfaction Models with a High Constraint Tightness. Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming, 17-31.
https://doi.org/10.1007/978-3-540-30201-8_5

[12]   Yong, G. and Joseph, C. (2007) Consistency and Random Constraint Satisfaction Models. Journal of Artificial Intelligence Research, 28, 517-557.

[13]   Achlioptas, D., Kirousis, L., Kranakis, E., Krizanc, D., Molloy, M. and Stamatiou, Y. (2001) Random Constraint Satisfaction: A More Accurate Picture. Constraints, 6, 329-344.
https://doi.org/10.1023/A:1011402324562

[14]   Xu, K. and Li, W. (2000) Exact Phase Transitions in Random Constraint Satisfaction Problems. Journal of Artificial Intelligence Research, 12, 93-103.

[15]   Xu, K. and Li, W. (2006) Many Hard Examples in Exact Phase Transitions. Theoretical Computer Science, 355, 291-302.

[16]   Xu, K., Boussemart, F., Hemery, F. and Lecoutre, C. (2007) Random Constraint Satisfac-tion: Easy Generation of Hard Satisfiable Instances. Artificial Intelligence, 171, 514-534.

[17]   Zhao, C. and Zheng, Z. (2011) Threshold Behaviors of a Random Constraint Satisfaction Problem with Exact Phase Transition. Information Processing Letters, 111, 985-988.

[18]   Frieze, A. and Wormald, N.C. (2005) Random k-sat: A Tight Threshold for Moderately Growing k. Combinatorica, 25, 297-305.
https://doi.org/10.1007/s00493-005-0017-3

[19]   Fan, Y. and Shen, J. (2011) On the Phase Transitions of Random k-Constraint Satisfaction Problems. Artificial Intelligence, 175, 914-927.

[20]   Fan, Y., Shen, J. and Xu, K. (2012) A General Model and Thresholds for Random Constraint Satisfaction Problems. Artificial Intelligence, 193, 1-17.

[21]   Zhao, C., Zhou, H., Zheng, Z. and Xu, K. (2011) A Message-Passing Approach to Random Constraint Satisfaction Problems with Growing Domains. Journal of Statistical Me-chanics: Theory and Experiment, 2011, 1742-5468.
https://doi.org/10.1088/1742-5468/2011/02/P02019

[22]   Zhao, C. and Zheng, Z. (2012) A Belief-Propagation Algorithm Based on Variable Entropy for Constraint Satisfaction Problems. Chinese Science: Information Science, 42, 1170-1180.

[23]   Zhao, C., Zhang, P., Zheng, Z. and Xu, K. (2012) Analytical and Belief-Propagation Studies of Random Constraint Satisfaction Problems with Growing Domains. Physical Review E Statistical Nonlinear & Soft Matter Physics, 85, Article ID: 016106.
https://doi.org/10.1103/PhysRevE.85.016106

 
 
Top