We study non-uniform random k-SAT on n variables with an arbitrary probability distribution p on the variable occurrences. The number t = t(n) of randomly drawn clauses at which random formulas go from asymptotically almost surely (a. a. s.) satisfiable to a. a. s. unsatisfiable is called the satisfiability threshold. Such a threshold is called sharp if it approaches a step function as n increases. We show that a threshold t(n) for random k-SAT with an ensemble (p_n)_(n∈N) of arbitrary probability distributions on the variable occurrences is sharp if ‖p_n‖_2~2 = O_n (t~(-2/k)) and ‖p_n‖_∞ = o_n (t~(-k/2k-1) · log~(-k-1/2k-1) t). This result generalizes Friedgut's sharpness result from uniform to non-uniform random k-SAT and implies sharpness for thresholds of a wide range of random k-SAT models with heterogeneous probability distributions, for example such models where the variable probabilities follow a power-law distribution.
展开▼
