
k 3 4 5 7 10 20

Theoretically derived bounds

2

k log 2 5.54 11.09 22.18 88.72 709.78 726,817

r¬*exist,k*[24] 4.51 10.23 21.33 87.88 708.94 726,817

r*exist,k*[25], [26] 3.52 7.91 18.79 84.82 704.94 726,809

2

k log 2 − k 2.54 7.09 17.18 81.72 699.78 706,817

r*poly,k* [27], [26] 3.52 5.54 9.63 33.23 172.65 95,263

Estimates

r¬*exist,k*[28] 4.267 9.93 21.12 87.79 708.91 - r1*RSB,k*[28], [29] 4.15 9.38 19.16 62.5 - -

TABLE I

CURRENT BEST UPPER/LOWER BOUNDS ON THE PHASE TRANSITION THRESHOLDS IN RANDOM K-SAT.

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

We now consider the performance of the CFL algorithm.

Fig. 2 gives median measurements of normalized stopping time (stopping time divided by N) of the CFL algorithm vs r=M/N when the number of variables N = 100. Fig. 3 gives median measurements of normalized stopping time vs N with r held constant. Data is shown for random k-SAT with k = 3, 4 and 5. Observe two striking features from this data. Firstly, from Fig. 2 noting that a log scale is used on the y-axis, the median normalized stopping time increases exponentially with r when N is held constant . Secondly, from Fig. 3 the median normalized stopping time vs N, with r held constant, is upper bounded by a constant. That is, a satisfying assignment is found in a time with median value that increases no more than linearly with N. This linearity holds even when r is close to r*exist,k* (data is shown in Fig. 3 for 3-SAT with r = 4) and is of great practical importance as it implies that with high probability the CFL algorithm finds a satisfying assignment in polynomial time.

Comparing the performance of the CFL algorithm with the popular WalkSAT algorithm, we note that the WalkSAT
algorithm also exhibits an exponential-like dependence of stopping time on r and linearity in N [30], [34], [33]. To allow comparison in more detail, median stopping time data taken from [30, Fig 2a] is marked on Fig. 2. For r < 3.9, the median stopping time is similar for CFL and WalkSAT.

Above this value, however, the stopping time for WalkSAT
diverges, increasing super-exponentially in r. This divergence is a feature not only of WalkSAT but also of other local search algorithms algorithms *e.g.* ChainSat [33]. It is not exhibited by the Survey Propagation algorithm [30], [8], which has been the subject of considerable interest as it creates the ability to operate close to the r*exist,k* threshold. Observe that the CFL
algorithm also does not exhibit divergence as r approaches r*exist,k*. These comparisons are encouraging as they indicate that the CFL algorithm is competitive with some of the most efficient general-purpose k-SAT algorithms currently available.

It is also unexpected as information sharing is a key component of both WalkSAT and Survey Propagation, whereas CFL
makes local decisions simultaneously with no use whatsoever of information-sharing, raising fundamental questions as to the role of message passing, the relationship between information exchange and algorithm performance and, in particular, what performance cost is imposed by constraining attention to decentralized operation.