There has been much recent interest in the satisfiability of random Boolean formulas. A random
k‐SAT formula is the conjunction of
m random clauses, each of which is the disjunction of
k literals (a variable or its negation). It is known that when the number of variables
n is large, there is a sharp transition from satisfiability to unsatisfiability; in the case of 2‐SAT this happens when
m/n → 1, for 3‐SAT the critical ratio is thought to be
m/n ≈ 4.2. The sharpness of this transition is characterized by a critical exponent, sometimes called
ν = νk (the smaller the value of ν the sharper the transition). Experiments have suggested that ν
3 = 1.5 ± 0.1. ν
4 = 1.25 ± 0.05, ν
5 = 1.1 ± 0.05, ν
6 = 1.05 ± 0.05, and heuristics have suggested that
νk → 1 as
k → ∞. We give here a simple proof that each of these exponents is at least 2 (provided the exponent is well defined). This result holds for each of the three standard ensembles of random
k‐SAT formulas:
m clauses selected uniformly at random without replacement,
m clauses selected uniformly at random with replacement, and each clause selected with probability
p independent of the other clauses. We also obtain similar results for
q‐colorability and the appearance of a
q‐core in a random graph. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 182–195, 2002
相似文献