Sharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT

Tobias Friedrich, Ralf RothenbergerIJCAI 2019 · DOI

TL;DR

This paper investigates the "sharpness" of the satisfiability threshold in random k-SAT problems, extending previous work from uniform to non-uniform variable distributions. They provide conditions under which this threshold remains sharp, offering a crucial step towards understanding the average-case complexity of SAT solvers for more realistic, non-uniform problem instances.

What Problem Does This Paper Address?

The Satisfiability Problem (SAT) is a fundamental problem in computer science, notorious for its computational difficulty. While SAT solvers can efficiently handle many real-world instances, theoretical worst-case analysis suggests these problems should be intractable. This discrepancy has led researchers to study the "average-case complexity" of SAT, often by generating random instances.

A key concept in this area is the "satisfiability threshold." For a given number of variables ($n$) and clauses ($m$), there's a critical ratio of clauses to variables ($m/n$) where random formulas transition from being almost surely satisfiable to almost surely unsatisfiable. The "sharpness" of this threshold refers to how abruptly this transition occurs. A sharp threshold means the probability of satisfiability changes from nearly 0 to nearly 1 over a very narrow range of $m/n$, resembling a step function.

Most prior work has focused on "uniform" random k-SAT, where all possible clauses are equally likely. However, real-world SAT instances often exhibit non-uniformities, particularly in how frequently variables appear. This paper addresses the question of whether the satisfiability threshold remains sharp for these more realistic "non-uniform" random k-SAT models, and under what conditions.

Methods

The authors generalize the concept of the satisfiability threshold to non-uniform random k-SAT models. They introduce two related models: the "clause-drawing model" and the "clause-flipping model." The core of their approach is to adapt and extend existing theoretical tools, particularly Friedgut's work on sharp thresholds for uniform random k-SAT.

Their main contribution is identifying specific conditions on the variable probability distribution (denoted by $p_n$) that guarantee a sharp satisfiability threshold. These conditions relate to the "norm" of the probability distribution, specifically the $L_\infty$ norm (maximum probability of any single variable) and the $L_2$ norm (a measure of how spread out the probabilities are). They leverage a version of Bourgain's Sharp Threshold Theorem, a powerful tool for proving sharpness in probabilistic settings. The proof involves ruling out "boosters" – subformulas that significantly increase the probability of unsatisfiability – by showing they either don't appear with sufficient probability or don't provide a large enough boost.

Datasets

Not discussed in the paper. The paper focuses on theoretical models of random instance generation rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Generalizing Sharpness: The paper successfully extends the notion of a sharp satisfiability threshold from uniform to non-uniform random k-SAT, a significant step towards understanding more realistic problem distributions.
  • Conditions for Sharpness: The identification of specific conditions on the variable probability distribution (related to its $L_\infty$ and $L_2$ norms) that guarantee sharpness is a key theoretical contribution. This provides a concrete framework for analyzing new models.
  • Bridging Theory and Practice: By studying non-uniform models, the work aims to bridge the gap between theoretical SAT models and the structure of industrial instances, potentially shedding light on why some real-world problems are easier to solve.
  • Technique Extension: The paper demonstrates how techniques developed for uniform random SAT, like Friedgut's sharpness proofs, can be adapted and generalized to more complex non-uniform settings.

Key Results

The paper presents three main theorems:

  • Theorem 1.2: Establishes that for the non-uniform clause-flipping model, the satisfiability threshold is sharp if the variable probability distribution ensemble $(p_n)_{n \in \mathbb{N}}$ satisfies certain conditions: $||p_n||_\infty = O(t^{2k-1} \log^{k-1} t)$ and $||p_n||_2 = O(t^{-2/k})$, where $t(n)$ is the asymptotic threshold function.
  • Theorem 1.3: Shows that the same sharpness result holds for the non-uniform clause-drawing model under the same conditions on the variable probability distribution.
  • Corollary 3.1: Applies Theorem 1.3 to power-law distributions with an exponent $\beta \geq \frac{2k-1}{k-1} + 1 + \epsilon$, demonstrating sharpness for a broad class of non-uniform instances.

The results indicate that the threshold is sharp for a fixed $n$, meaning the probability of satisfiability transitions abruptly around a specific value of the scaling parameter ($s$ or $m$).

Limitations and Future Work

  • Fixed $n$ Sharpness: The paper's sharpness result is for a fixed $n$. It's noted that this doesn't automatically prove the satisfiability threshold conjecture for all $n$, as the threshold function might oscillate for different values of $n$.
  • Sufficient Conditions: The paper provides sufficient conditions for sharpness. It would be interesting to find necessary and sufficient conditions, or to characterize when the threshold is coarse.
  • Conjecture Proof: While this work provides a crucial ingredient (sharpness) for proving the satisfiability threshold conjecture for non-uniform models, it doesn't complete the proof itself. Future work could aim to derive proofs of the conjecture for specific non-uniform ensembles.
  • Generalization of Techniques: The authors suggest that their techniques might be adaptable to analyze other sophisticated models, like the popularity-similarity model.

Summary updated

BibTeX
@inproceedings{friedrich2019sharpness,
  author = {Tobias Friedrich and Ralf Rothenberger},
  title = {{Sharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/853},
}
Figure