Satisfiability Decay along Conjunctions of Pseudo-Random Clauses

k-SAT is a fundamental constraint satisfaction problem. It involvesS(m), the satisfaction set of the conjunction of m clauses,each clause a disjunction of k literals. The problem has manytheoretical, algorithmic and practical aspects. When the clauses are chosen at random it is anticipated (butnot fully proven) that, as the density parameter m/n (n thenumber of variables) grows, the transition of S(m) to beingempty, is abrupt: It has a "sharp threshold", with probability1 – o(1). In this article we replace the random ensemble analysis by apseudo-random one: Derive the decay rule for individual sequencesof clauses, subject to combinatorial conditions, which in turnhold with probability 1 – o(1). This is carried out under the big relaxation that k is not constantbut k = log n , or even r log log n . Then the decay of S isslow, "near-perfect" (like a radioactive decay), which entailssharp thresholds for the transition-time of S below any givenlevel, down to S = .