Delaying satisfiability for random 2SAT. Issue 2 (24th September 2012)

• Record Type: Journal Article
• Authors: Sinclair, Alistair; Vilenchik, Dan
• Is Part Of: Random structures & algorithms. Volume 43:Issue 2(2013)
• Page Start: 251
• Page End: 263
• Publication Date: 2012-09-24
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20465
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>Let (<italic>C</italic><sub>1</sub>, <italic>C</italic>′<sub>(*)</sub>), (<italic>C</italic><sub>2</sub>, <italic>C</italic>′<sub>(*)</sub>), …, (<italic>C</italic><sub><italic>m</italic></sub>, <italic>C</italic>′<sub>(*)</sub>) be a sequence of ordered pairs of 2CNF clauses chosen uniformly at random (with replacement) from the set of all 4 <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath} \pagestyle{empty} \begin{document} \begin{align*}\binom{n}{2}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg277vcjnh" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> clauses on <italic>n</italic> 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 <italic>whp</italic> in a satisfiable 2CNF formula as long as <italic>m</italic>/<italic>n</italic> ≤ (1000/999)<sup>1/4</sup>. This contrasts with the well‐known fact that a random <italic>m</italic> ‐clause formula constructed without the choice of two clauses at each step is unsatisfiable <italic>whp</italic> whenever <italic>m</italic>/<italic>n</italic> > 1. Thus the choice algorithm is able to <italic>delay</italic> 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 <italic>m</italic> 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 <italic>k</italic> ‐SAT for any fixed <italic>k</italic> coincides with the standard satisfiability threshold for random 2<italic>k</italic> ‐SAT.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013</p> </abstract>