Mick Gets Some (the Odds Are on His Side)

Abstract

Consider a randomly generated boolean formula F (in the conjunctive normal form) with m clauses of size k over n variables; k is fixed at any value greater than 1, but n tends to ininity and m = (1 + o(1))cn for some c depending only on k. It is easy to see that F is unsatisfiable with probability 1 - o(1) whenever c > (1n2)2"k; we complement this observation by proving that F is satisfiable with probability 1 - o(1) whenever c < (0.25)2"k/k; in fact, we present a linear-time algorithm that satisfies F with probability 1 - o(1). (This result is a continuation of work by Chao and Franco.) In addition, we establish a threshold for 2-SAT; if k = 2 then F is satisfiable with probability 1 - o(1) whenever c < 1 and unsatisfiable with probability 1 - o(1) whenever c > 1. (orig.)