Sharpness of the Satisfiability Threshold for Non-uniform Random κ-SAT

摘要

We study non-uniform random κ-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. unsatisfi-able 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.