Phase Transitions of Bounded Satisfiability Problems

1 Introduction and Summary of Results

A phase transition of a "system" can be described as an abrupt change in the behavior of the system that occurs when a cer­ tain "control parameter" is at or near a certain critical value. Traditionally, phase transitions have been studied by physi­ cists working in the area of statistical mechanics. During the past decade, however, computer scientists have carried out an intensive study of phase transitions of algorithmic problems, first of NP-complete decision problems and, more recently, of decision problems that are complete for higher compu­ tational complexity classes. These investigations have shed new light on the "structure" of presumably intractable deci­ sion problems by examining them from a perspective that had been hitherto unexplored in computer science; moreover, for certain fundamental algorithmic problems, the location of the phase transition has been correlated to the peak average cost of natural algorithms for solving these problems.

· Research of the authors was partially supported by NSF Grant No. IIS-9907419

The Boolean satisfiability problems kSAT, k > 3, con­ stitute the most thoroughly investigated collection of NP­ complete problems from the perspective of phase transitions. An instance of kSAT is a kCNF formula; the "control param­ eter" of such a formula is the ratio of the number of clauses over the number of variables occurring in the formula. Each fixed valuer of this ratio gives rise to the family of probabil­ ity spaces Fk(n,r), n 2 1, where Fk(n,r) is the collect~on of all kCNF-formulas with rn clauses generated by selectmg k variables from n variables without replacement and then negating each variable with probability 1/2. Franco and Paul [Franco and Paul, 1983] were the first to focus on this fixed clauses-to-variables ratio model and to initiate a study of the asymptotic behavior of the probability Pk ( n, r) that a random formula in Fk ( n, r) is satisfiable. During the past decade, much of the work in this area has been motivated from the conjecture of Chvatal and Reed [Chvatal and Reed, 1992] to the effect that, for every k 2 3, there is a positive real number rk such that ifr < rk> then limn-+oo Pk(n,r) = 1, whereas ifr > rk> thenlimn-+ooPk(n,r) = 0.

The above conjecture asserts that, for every k 2 3, a phase transition occurs in the probability Pk(n, r) of a ran­ dom formula in Fk(n , r) being satisfiable, as n ---+ oo. In spite of intensive efforts by several researchers, this conjec­ ture has not been settled thus far. Nonetheless, progress to­ ward establishing this conjecture has been made in two dif­ ferent fronts. On the experimental front, large-scale experi­ ments with random Boolean formulas have provided evidence for the existence of a critical ratio rk and have yielded esti­ mates of its actual value. In particular, experiments by Sel­ man, Mitchell and Levesque [Selman et al., 1996] with ran­ dom 3CNF-formulas and analysis of these experiments by Kirkpatrick and Selman [Kirkpatrick and Selman, 1994] in­ dicate that r3 is about 4.2. On the analytical front, there has been continuous progress toward establishing progres­ sively tighter upper and lower bounds for the value of r3. The best analytical results obtained to date assert that if r3 exists, then 3.42 < r3 < 4.507 [Kaporis et al., 2002; Dubois et al., 2000]. The experiments carried out by Sel­ man, Mitchell and Levesque [Selman et al., 1996] for random 3CNF-formulas also revealed that the critical ratio 4.2 ap­ pears to be the location at which the average cost of the Davis­ Putnam-Logemann-Loveland (DPLL) procedure for Boolean satisfiability peaks.

Many fundamental algorithmic problems are optimization problems and not mere decision problems. In particular, if a Boolean formula happens to be over-constrained and, thus, unsatisfiable, it is natural to ask for the maximum number of clauses in the formula that can be simultaneously satis­ fied. By focusing on 3CNF-formulas, we obtain the optimiza­ tion problem MAX 3SAT: given a 3CNF-formula <p, find the maximum number of clauses of <p that can be simultaneously satisfied. MAX 3SAT is a prototypical constraint optimiza­ tion problem that is known to play a prominent role in the study of the approximability properties of NP-optimization problems. Indeed, as shown by Papadimitriou and Yan­ nakakis [Papadimitriou and Yannakakis, 1991], MAX SAT is a MAX SNP-complete problem; this means that MAX SAT is a constant-approximable optimization problem and that ev­ ery NP-optimization problem in the class MAX SNP can be reduced to it via an approximation-preserving polynomial­ time reduction (see also [Papadimitriou, 1994]).

Its importance in complexity and approximability notwith­ standing, MAX 3SAT had not been investigated from the perspective of phase transitions until recently. Zhang [Zhang, 200 I] was the first to investigate phase transitions for MAX 3SAT by carrying out an initial set of experiments for the family of bounded satisfiability problems 3SAT(b), where b is a non-negative integer. An instance of 3SAT(b) is a 3CNF­ formula <p and the question is: does there exist a truth assign­ ment that violates no more than b clauses of <p? Equivalently, 3SAT(b) asks whether the optimum value of MAX SAT on an instance <p is at least m - B, where m is the number of clauses of <p. Thus, each 3SAT(b) is a decision problem ob­ tained from MAX SAT by imposing a "quality bound" on the optimum value. The control parameter of each 3SAT(b) is the ratio of clauses to variables, that is, the same control parameter as the one used for 3SAT.

Zhang [Zhang, 2001] explored phase transitions for the bounded satisfiability problems 3SAT(b) by running exper­ iments on random 3CNF-formulas with n = 25 variables and forb = 5, 10, 15, 20. His findings suggest that there is a se­ ries of separated phase transitions corresponding to different quality bounds. The location of each phase transition appears to increase with b (see Figure 7); moreover, the average cost for solving the optimization problem MAX SAT appears to be the envelope of the peak average cost for solving the deci­ sion problems 3SAT(b), as b increases. Zhang [Zhang, 2001] did not report on the asymptotic behavior of 3SAT(b) as the number of variables increases, because he ran experiments for just a single value (n = 25) of the number of variables. He posed the analysis of phase transitions for 3SAT(b) as an open problem and, in particular, raised the question of finding the exact location of the phase transitions for these decision problems.

In this paper, we report on a systematic investigation of phase transitions for the family of bounded satisfiability prob­ lems 3SAT(b) . Our investigation has produced both ana­ lytical and experimental results that yield a more complete and, at the same time, rather surprising picture of these phase transitions. As stated above, Zhang's [Zhang, 2001] initial experiments suggest that the location of the phase transition for each 3SAT(b) increases with b. Here, using the firstmoment method, we show analytically that the phase tran­ sitions for 3SAT(b) must occur (if they occur at all) within a rather narrow region, regardless of the value of b. More­ over, the same behavior is exhibited by the families kSAT(b) of decision problems underlying the optimization problems MAX kSAT, k ~ 3. In particular, the locations of the phase transitions for 3SAT(b) are bounded from above by 1/(3- lg(7)) ~ 5.19 and from below by the greatest known lower bound 3.42 for the location of the phase transition for 3SAT. At the experimental front, we investigated the asymp­ totic behavior of 3SAT(b) for the values b = 3, 4 and 5 by running experiments for several different values of the num­ ber n of variables of random 3CNF-formulas (n = 10, 15, 20, 25, 30, 35). Our most striking experimental finding is the discovery that, as n increases, the phase transition for each 3SAT(b) emerges in a manner that is qualitatively different from that for 3SAT, as we describe next.

In the case of 3SAT, the experiments in [Selman et al. , 1996] revealed that the family of curves for the probability of satisfiability of a random 3CNF-formula (one curve for each number n of variables) has the property that the curves be­ come progressively steeper and every two of them intersect at a single point whose abscissa is near the location of the phase transition for 3SAT (see Figure 1). In contrast, our ex­ periments reveal that, for each bounded satisfiability problem 3SAT(b), the family of curves for the probability of a "yes" answer of a random 3CNF-formula (one curve for each num­ ber n of variables) become progressively steeper but they do not intersect; instead, they are separated by a distance that is getting smaller as n increases. Figures 2, 3, and 4 depict these findings for 3SAT(3), 3SAT(4) and 3SAT(5), respec­ tively. This is a qualitatively different pattern of emergence of a phase transition that does not seem to have been encoun­ tered in earlier investigations of phase transitions of other NP­ complete problems in which the probability curves appear to have a quasi-common intersection point.

2 Bounded Satisfiability Problems

For every positive integer k ~ 3, MAX kSAT is the follow­ ing optimization problem: given a kCNF-formula <p, find the maximum number of simultaneously satisfied clauses of cp. The study of phase transitions for an optimization problem begins by focusing on one or more decision problems that underlie that optimization problem. The most natural way to derive a decision problem from an optimization problem is to consider as input both an instance of the optimization prob­ lem and an arbitrary quality bound, and to ask whether the optimum value on this instance is bigger (or smaller) than the given quality bound. In the case of MAX kSAT, this gives rise to the following NP-complete decision problem: given a kCNF-formula <p and an integer c, is there a truth assignment to the variables of <p that satisfies at least c clauses of cp? It is also possible to derive a family of decision problems that underlie MAX kSAT and are such that the inputs to each of them are kCNF-formulas only. For each non-negative integer b, let kSAT(b) be the following bounded satisfiability prob­ lem: given a kCNF-formula <p, is there a truth assignment to the variables of <p that violates no more than b clauses of r.p? Clearly, kSAT(O) is kSAT itself; moreover, 1t IS easy to show that every bounded satisfiability problem kSAT(b), where k 2: 3 and b 2: 1, is NP-complete. Since the input to kSAT(b) is a kCNF-formula, phase transitions for the family kSAT(b) can be studied using the ratio of clauses to variables as the control parameter, that is, the same control parameter as the one used in the study of phase transitions for kSAT.

There have been earlier investigations of phase transi­ tions for other fundamental optimization problems, includ­ ing the TRAVELING SALESMAN PROBLEM [Gent and Walsh, 1996b] and NUMBER PARTITIONING [Gent and Walsh, 1996al. It should be noted, however, that for each of these two optimization problems a single decision problem was considered (instead of a family of decision problems) because the quality bound was part of the input to the decision prob­ lem. Moreover, the control parameter for these problems was chosen in such a way that it encoded the quality bound in some direct or indirect way, and this choice was criticized in subsequent investigations [Slaney and Thiebaux, 1998]. Clearly, this criticism does not apply to the bounded satis­ fiability problems kSAT(b).

For every integers k 2: 3, n 2: 1, and b 2: 0, let Prk[n, r, b] be the probability that a random formula r.p in the space Fk(n,r) is a "yes" instance of kSAT(b), that is, there is a truth assignment that violates no more than b clauses of r.p. We now have all the notation in place to formulate the follow­ ing conjecture concerning phase transitions for the bounded satisfiability problems kSAT(b).

Conjecture 2.1: For every integer k 2: 3 and every integer b 2: 0, there is a positive real number rk,b such that

• If r < rk,b. then limn-too Prk[n, r, b] = 1;
• If r > rk,b. then limn-too Prk[n, r, b] = 0.

Note that Chvatal and Reed's conjecture [Chvatal and Reed, 1992] concerning phase transitions for kSAT, k 2: 3, is the special case of Conjecture 2.1 in which b = 0. As men­ tioned in Section 1, Zhang [Zhang, 200 1] raised the prob­ lem of finding the exact location of the phase transition for 3SAT(b), which, in terms of the notation introduced here, amounts to first establishing Conjecture 2.1 for k = 3 and then determining the critical ratio r3 ,b, for each b. Although far from solving these problems, the next result yields ana­ lytical upper bounds for the values of rk,b; in particular, it demonstrates that for each k 2: 3, all critical ratios rk ,b are bounded by a quantity that depends only on k.

Proposition 2.2: Fix two integers k 2: 3 and b 2: 0.

• lfr > k-lg(~k_ 1 ), then limn-too Prk[n, r, b] = 0.
• Consequently, ifrk,b exists, then rk,b :::; k-lg(~L 1 )' regardless of the value of b.

Proof: If X is a random variable taking non-negative values and having finite expectation E(X), then Markov's inequal­ ity asserts that Pr[X 2: 1] :::; E(X). This inequality has been used in the past to obtain a coarse upper bound for the criti­ cal ratio rk for the phase transition of kSAT. Here, we will apply the same method to obtain upper bounds for the criti­ cal ratios rk ,b for the phase transitions of kSAT(b). In this case, however, bounding the expectation of a suitable random variable X is not as trivial as it was for kSAT, but still quite straightforward.

Let x;·r,b be a random variable on Fk(n,r) such that if r.p is a formula in Fk(n, r), then x;·r,b(r.p) is the number of truth assignments on n variables that violate no more than b clauses of r.p. Clearly, Prk[n, r, b] = Pr[x;·r,b 2: 1], thus our goal now is to bound the expectation E(x;·r,b).

For every truth assignment a on n variables, let I~ be the Bernoulli random variable on Fk(n, r) such that I~(r.p) = 1, if a violates no more than b clauses of r.p, and I~ ( r.p) = 0, otherwise. It is easy to see that the number of formulas in Fk(n, r) for which a violates no more than b clauses is L:~=o Cn)(~) i ( (2k - 1) (~) rn-i, which implies that

Since x;·r,b = ~a I~, the linearity of expectation implies that E(x;·r,b ) = ~aE(I~) = 2n E(I~). Thus,

Consequently,

Th "f 1 h 1" E(Xn,r,b) - 0 us, 1 r > k-lg( 2 k_ 1 ), t en Imn---too k - , regardless of the value of b. Now an application of Markov's inequality to x;·r,b gives the result. I

Concerning lower bounds for rk,b, it is obvious that if r is a ratio such that almost all kCNF-formulas are satisfiable, then limn-too Prk[n, r, b] = 1, regardless of the value of b. Consequently, if rk is the critical ratio for kSAT, then rk :::; rk,b. regardless of the value of b. Of course, this assumes that the critical ratios rk and rk,b actually exist. Until this is established, we can use the analytically derived lower bounds for rk as lower bounds for every rk,b· In particular, the best currently known such lower bound for r 3 is 3.42 [Kaporis et al., 2002]. By combining these remarks with Proposition 2.2, we obtain the following bounds for the phase transitions of the bounded satisfiability problems 3SAT(b) .

Corollary 2.3: Let b 2: 0 be an integer.

• /fr < 3.42, then limn-too Pr3[n, r, b] = 1
• lfr > 3 _ 1~(7) ~ 5.19, then limn-too Pr3[n, r, b] = 0.

Consequently, if r3,b exists, then 3.42 :::; r3,b :::; 5.19, regard­ less of the value of b.

3 Experimental Results

We ran experiments for random 3CNF-formulas drawn from n = 10, 15, 20, 25, 30 and 35 variable spaces. We imple­ mented a suitably modified version of the Davis-Logemann­ Loveland-Putnam (DPLL) procedure and tested each random formula drawn to determine whether it is a "yes" instance of the bounded satisfiability problems 3SAT(b), forb = 3, 4 and 5. For each (n, b)-pair, probability curves were deter­ mined by recording the average number of "yes" instances in samples of 1200 formulas, one sample for each possible ratio of clauses to variables up to a ratio of 15.

The probability curves for 3SAT(b) with b = 3, 4 and 5 are depicted in Figures 2, 3 and 4, respectively.

ln these figures, we see that, as r increases, the probability curves start out in a region where the probability is 1 or close to 1 and then they transition to a region where the probability is 0 or close to 0. To make the terminology more precise, let us define the location of the transition for the probability of 3SAT(b) to be the ratio rat which the probability is 0.5, and the width of the transition for the probability of 3SAT(b) to be the difference in the r values between the ratios at which the probability falls from 0.9 to 0.1. As n increases, the probabil­ ity curves move from right to left; moreover, both the location and the width of the transition appear to change with different values of n . For each fixed b, the width becomes smaller with increasing n just as is the case for the probability curves for 3SAT in Figure l; the location, however, moves dramatically to the left in sharp contrast with the behavior for 3SAT, where the location moves very slightly and converges to a value in the transition region where all the curves appear to intersect at one point. The magnitude of the leftward movement of the transition location with increasing n appears to become greater with increasing values of b. Thus, the phase transi­ tions for the bounded satisfiability problems 3SAT(b) emerge in a pattern that is novel and qualitatively different from that of the phase transitions for other NP-complete problems.

We also recorded the average cost of the modified DPLL­ procedure for solving 3SAT(b), where b = 3, 4, 5. Each of these problems is much harder on average than 3SAT; more­ over, these problems are getting harder on average as b in­ creases. As a matter of fact, the experiments for b = 5 and for n = 35 took several weeks to complete. Figure 5 depicts the average cost of solving 3SAT, while Figures 6 depicts the average cost of solving 3SAT(5).

In Figure 6, the performance curves for 3SAT(5) move from lower to higher with increasing n and, as has been ob­ served with 3SAT, the peaks in cost appear to correspond to the location of the transitions. The peaks move from right to left in synchrony with the movement of the location of the transition for 3SAT(b); this movement is more dramatic than in the case of 3SAT.

4 Finite Size Scaling

The locations of the transition in the probability curves for 3SAT(b) appear to approach a limiting critical ratio r3 ,b that is within the analytically derived upper and lower bounds in Corollary 2.3. Nonetheless, it is not clear what the critical ratio r3,b actually is, nor can it be estimated by visual inspection since no two probability curves for 3SAT(b) intersect. A finite-size scaling analysis of the data, assuming a power law of the form (r-r 3 b)n"J, b , allowed us to obtain estimates for r3,b both the critical ratio r3 ,b and for the exponent v3 ,b, where b = 3, 4 and 5.

In [Kirkpatrick and Selman, 1994], an estimate for the value of the critical ratio rk was obtained by visually estimat­ ing the point at which the probability curves for kSAT appear to intersect, and then regression techniques were applied to determine the best exponent vk in the power law for kSAT. This cannot be done with the bounded satisfiability problems 3SAT(b), since the probability curves do not intersect, but appear to be moving to the left as the number n of variables increases. Nevertheless the finite-size scaling hypothesis can still be tested with a more elaborate procedure. Our goal was to test whether it is possible find values for r3,b and v 3 ,b such that when the ratio r is rescaled with the above power law, the probability curves for the different values n of the number of variables collapse to a single curve. Using routines for in­ terpolation and regression from Matlab, we stepped through small increments of putative r3 ,b values and measured how well the curves collapsed to a single curve by calculating the sum of their pairwise squared differences when accordingly transformed. The estimated r3 ,b was taken to be the value that minimized this difference measure. We found this tech­ nique to be well behaved, in that it exhibited a clear min­ imum and gave much more precision than visually judging how well the curves appeared to collapse to a single curve. To further validate this technique, we checked it on the phase transition of 2SAT, which has been analytically determined to occur at the critical ratio r 2 = 1 [Chvatal and Reed, 1992; Fernandez de Ia Vega, 1992; Goerdt, 1996]. The agreement was very good, namely, the estimate for r 2 was 0.98.

The results of the finite-size scaling analysis for 3SAT(b) , where b = 3, 4 and 5, are shown in Table I . Note that these results are consistent with the analytical upper and lower bounds for r 3,b in Corollary 2.3, that the rb ,k are in the re­ gion between rk fork-SAT and the Markov upper bound for k-SAT. This consistency is the most that can _be reasonably concluded from the finite-size scaling analysis. The tech­ nique provides a more principled way to make the estimates than eyeballing, but no great accuracy should be attributed to the estimates in spite of their apparent precision. Although the finite-size scaling results suggest that the locations of the phase transitions of 3SAT(b) are different for different b's, it may still be the case that they all coincide with the location for 3SAT.

5 Concluding Remarks

The results reported here advance the understanding of the phase transitions for the family of bounded satisfiability prob­ lems 3SAT(b), introduced by Zhang [Zhang, 2001],

Our main analytical finding is that the phase transitions of all 3SAT(b) problems must occur within a narrow region, re­ gardless of how large the value of b is. Moreover, our exper­ iments revealed that the phase transitions for these problems occur in a remarkable way. Specifically, unlike 3SAT, the probability curves for 3SAT(b) do not have a quasi-common intersection point about which they rotate as they become steeper with increasing n. Instead, they move rapidly to the left toward the narrow region that the analysis predicts.

Identifying the exact locations of the phase transitions for 3SAT(b) remains an open problem, which is at least as hard as identifying the location of the phase transition for 3SAT. Equally hard appears to be the problem of analytically es­ tablishing whether these locations are separated or coincide. Nonetheless, it may be possible to analytically obtain tighter bounds for these locations using some of the sophisticated techniques that have been quite successful in finding tighter bounds for the phase transition of 3SAT.

Acknowledgments: We are grateful to Victor Dalmau for stimulating and insightful discussions. We also wish to thank the reviewers for their many useful comments and sugges­ tions.