Weak lumpability in the k-SAT problem

Introduction The k-SAT problem, a good introduction to which is in [7], is as follows: Assume that we are given a set of n literals (Boolean variables) fs 1 ; : : : ; s n g. Choosing each time k of these, we create m clauses (conjunctions). The question is to find an assignment of these variables such that the disjunction of all the clauses is true. There is a very intriguing observation. Define P(n; k; m) to be the probability that a k-SAT problem in n literals having m clauses has a solution. Then the limit f(c; k) = lim n!1 P(n; k; nc) exists for all c ? 0. Furthermore, the function f(c; k) is piecewise constant, taking the value 1 for c<F