Delaying satisfiability for random 2SAT

Let ( C 1 , C ′ (*) ),( C 2 , C ′ (*) ),…,( C m , C ′ (*) ) be a sequence of ordered pairs of 2CNF clauses chosen uniformly at random (with replacement) from the set of all 4 \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath} \pagestyle{empty} \begin{document} \begin{align*}\binom{n}{2}\end{align*} \end{document} clauses on n variables. Choosing exactly one clause from each pair defines a probability distribution over 2CNF formulas. The choice at each step must be made on‐line, without backtracking, but may depend on the clauses chosen previously. We show that there exists an on‐line choice algorithm in the above process which results whp in a satisfiable 2CNF formula as long as m / n ≤ (1000/999) 1/4 . This contrasts with the well‐known fact that a random m ‐clause formula constructed without the choice of two clauses at each step is unsatisfiable whp whenever m / n > 1. Thus the choice algorithm is able to delay satisfiability of a random 2CNF formula beyond the classical satisfiability threshold. Choice processes of this kind in random structures are known as “Achlioptas processes.” This paper joins a series of previous results studying Achlioptas processes in different settings, such as delaying the appearance of a giant component or a Hamilton cycle in a random graph. In addition to the on‐line setting above, we also consider an off‐line version in which all m clause‐pairs are presented in advance, and the algorithm chooses one clause from each pair with knowledge of all pairs. For the off‐line setting, we show that the two‐choice satisfiability threshold for k ‐SAT for any fixed k coincides with the standard satisfiability threshold for random 2 k ‐SAT.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013