On the Satisfiability of Random 3-SAT Formulas with k-Wise Independent Clauses - Abstract

Q: What distinguishes this work from the classical random 3-SAT model?

The clause signs/literals are still drawn uniformly, but the analysis relaxes full independence by enforcing k-wise independence among clauses rather than complete independence.

Q: How are the families of distributions Fk(n,m) defined?

Fk(n,m) contains probability distributions that generate formulas with m clauses, where each clause is uniformly sampled from all 3-literal sets over n variables, and the resulting clauses are k-wise independent.

Q: What are the main satisfiable/unsatisfiable regimes identified for different k values?

For k=2 and m on the order of n^3, formulas are unsatisfiable with high probability; there exists a k=3 construction with m on the order of n^3 that is almost always satisfiable; for k=4 and m on the order of n^2, formulas are unsatisfiable with high probability; for any k≥2 with m=O(n^(1-1/k)), formulas are satisfiable with high probability.

Sep 14, 2026

Uploaded by Eliana

Random 3-SAT satisfiability thresholds are studied beyond the standard clause independence assumption by allowing each clause to remain uniformly random while enforcing k-wise independence. For parameters n, m, and k, distributions producing m uniformly sampled 3-literal clauses whose clauses are k-wise independent are denoted by Fk(n,m). The results give high-probability unsatisfiability for all D in F2(n,m) when m is on the order of n^3, tightness via a satisfiable construction for F3, and strong unsatisfiability for F4 when m is on the order of n^2, plus satisfiability for Fk with m = O(n^(1-1/k)).

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages26

Reading Time1 h 6 min

AccessFree to download

Abstract

Introduction

Random SAT

Relaxation of independence

On the satis􀀌ability of random 3-SAT formulas with k-wise independent clauses arXiv :2411 .03813v1 [math .CO] 6 Nov 2024 Ioannis Caragiannis Nick Gravin Zhile Jiang Abstract The problem of identifying the satis􀀌ability 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 signi􀀌cantly from the independence assumption and consider richer families of probability distributions. For integer parameters n, m, and k , we denote by Fk (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 satis􀀌ability or unsatis􀀌ability of formulas produced by distributions in Fk (n, m) for di􀀋erent values of the parameters n, m, and k. Our technical results are as follows: First, all probability distributions in F2 (n, m) with m ∈ 􀀊(n3 ) return unsatis􀀌able formulas with high probability. This result is tight. We show that there exists a probability distribution D ∈ F3 (n, m) with m ∈ O (n3 ) so that a random formula drawn from D is almost always satis􀀌able. In contrast, for m = 􀀊(n2 ), any probability distribution D ∈ F4 (n, m) returns an unsatis􀀌able formula with high probability. This is our most surprising and technically involved result. Finally, for any integer k ≥ 2, any probability distribution D ∈ Fk (n, m) with m = O (n1􀀀1/k) returns a satis􀀌able formula with high probability. 1 Introduction Satis􀀌ability of propositional formulas (SAT) is one of the most renowned problems in theoretical computer science. It appeared in the 􀀌rst lists of NP-complete problems independently proposed by Cook and Levin, and is pivotal for many developments in modern complexity theory. Today, many lower bounds on the running time of algorithms rely on the Exponential Time Hypothesis for solving SAT [11, 18, 36, 37] . On the practical side, SAT solvers are frequently deployed in hardware circuit design, model checking, program veri􀀌cation, automated planning and scheduling, as well as in solving real-life instantiations of combinatorial optimization problems such as FCC spectrum auctions. Modern SAT solvers often 􀀌nd solutions to large industrial instances with thousands or even millions of variables despite the NP-hardness of the problem. However, there is still a large discrepancy between the performance of SAT solvers on those instances and theoretical average-case predictions, which have been studied in great depth under the line of research on random SAT. Random SAT. A j-CNF formula φ over n variables is composed of m OR-clauses, each containing exactly j literals of j di􀀋erent variables. In the most commonly studied random SAT model, a formula φ is generated uniformly at random from all possible j-CNF formulas over n variables and m clauses. The most prominent theoretical question related to random SAT is to identify the satis􀀌ability threshold rj such that limn→∞ Pr [φ is satis􀀌able] is equal to 0 when m/n > rj , and equal to 1 when m/n < rj . It has been established [15] that 2-SAT has r2 = 1, and its phase transition window [10] is m ∈ [n−􀀂(n1/3) , n+􀀂(n1/3)] . For j ≥ 3, the asymptotic j-SAT threshold was shown to be 2j log 2 − ~~1~~2(1 + log 2) ± oj(1) as j → ∞ [17] (improving previous results from [3]), while for large enough j the exact value of rj was determined in [20] . However, the question of identifying rj for small values of j remains open. In particular, random 3-SAT has attracted a lot of attention.

FAQs

What distinguishes this work from the classical random 3-SAT model?

The clause signs/literals are still drawn uniformly, but the analysis relaxes full independence by enforcing k-wise independence among clauses rather than complete independence.

How are the families of distributions Fk(n,m) defined?

Fk(n,m) contains probability distributions that generate formulas with m clauses, where each clause is uniformly sampled from all 3-literal sets over n variables, and the resulting clauses are k-wise independent.

What are the main satisfiable/unsatisfiable regimes identified for different k values?

For k=2 and m on the order of n^3, formulas are unsatisfiable with high probability; there exists a k=3 construction with m on the order of n^3 that is almost always satisfiable; for k=4 and m on the order of n^2, formulas are unsatisfiable with high probability; for any k≥2 with m=O(n^(1-1/k)), formulas are satisfiable with high probability.

Sep 14, 2026

Uploaded by Eliana