Satisfiability Decay along Conjunctions of Pseudo-Random Clauses
Institute of Mathematics and School of Computer Science, The Hebrew University of Jerusalem, Israel.
 |
Abstract |
|---|
k-SAT is a fundamental constraint satisfaction problem. It involves S(m), the satisfaction set of the conjunction of m clauses, each clause a disjunction of k literals. The problem has many theoretical, algorithmic and practical aspects.
When the clauses are chosen at random it is anticipated (but not fully proven) that, as the density parameter m/n (n the number of variables) grows, the transition of S(m) to being empty, is abrupt: It has a "sharp threshold", with probability 1 – o(1).
In this article we replace the random ensemble analysis by a pseudo-random one: Derive the decay rule for individual sequences of clauses, subject to combinatorial conditions, which in turn hold with probability 1 – o(1).
This is carried out under the big relaxation that k is not constant but k = 
log n , or even r log log n . Then the decay of S is slow, "near-perfect" (like a radioactive decay), which entails sharp thresholds for the transition-time of S below any given level, down to S = 
.
Key Words: Constraint satisfaction • k-SAT • sharp thresholds • pseudorandom analysis • unique k-SAT representations • learning from examples