On the random satisfiable process Academic Article uri icon


  • Abstract In this work we suggest a new model for generating random satisfiable k-CNF formulas. To generate such formulas. randomly permute all possible clauses over the variables x 1,..., xn, and starting from the empty formula, go over the clauses one by one, including each new clause as you go along if, after its addition, the formula remains satisfiable. We study the evolution of this process, namely the distribution over formulas obtained after scanning through the first m clauses (in the random permutation's order).

publication date

  • September 1, 2009