Search Results

The problem of identifying the satisfiability threshold of random 3-SAT formulas has received a lot of attention during the last decades and has inspired the study of other threshold phenomena in random combinatorial structures. The classical assumption in this line of research is that, for a given set of n Boolean variables, each clause is drawn uniformly at random among all sets of three literals from these variables, independently from other clauses. Here, we keep the uniform distribution of each clause, but deviate significantly from the independence assumption and consider richer families of probability distributions. For integer parameters n, m, and k, we denote by ℱ_k(n,m) the family of probability distributions that produce formulas with m clauses, each selected uniformly at random from all sets of three literals from the n variables, so that the clauses are k-wise independent. Our aim is to make general statements about the satisfiability or unsatisfiability of formulas produced by distributions in ℱ_k(n,m) for different values of the parameters n, m, and k. Our technical results are as follows: First, all probability distributions in ℱ₂(n,m) with m ∈ Ω(n³) return unsatisfiable formulas with high probability. This result is tight. We show that there exists a probability distribution 𝒟 ∈ ℱ₃(n,m) with m ∈ O(n³) so that a random formula drawn from 𝒟 is almost always satisfiable. In contrast, for m ∈ Ω(n²), any probability distribution 𝒟 ∈ ℱ₄(n,m) returns an unsatisfiable formula with high probability. This is our most surprising and technically involved result. Finally, for any integer k ≥ 2, any probability distribution 𝒟 ∈ ℱ_k(n,m) with m ∈ O(n^{1-1/k}) returns a satisfiable formula with high probability.