Rigorous results for random (2+p)-SAT

In recent years there has been significant interest in the study of random k-SAT formulae. For a given set of n Boolean variables, let B-k denote the set of all possible disjunctions of k distinct, non-complementary literals from its variables (k-clauses). A random k-SAT formula F-k(n, m) is formed by selecting uniformly and independently m clauses from Bk and taking their conjunction. Motivated by insights from statistical mechanics that suggest a possible relationship between the "order" of phase transitions and computational complexity, Monasson and Zecchina (Phys. Rev. E 56(2) (1997) 1357) proposed the random (2 + p)-SAT model: for a given p is an element of [0, 1], a random (2 + p)-SAT formula, F2+p(n, m), has nt randomly chosen clauses over n variables, where pm clauses are chosen from B-3 and (1 - p)m from B-2. Using the heuristic "replica method" of statistical mechanics, Monasson and Zecchina gave a number of non-rigorous predictions on the behavior of random (2 + p)-SAT formulae. In this paper we give the first rigorous results for random (2 + p)-SAT, including the following surprising fact: for p less than or equal to 2/5, with probability 1 - o(l), a random (2 + p)-SAT formula is satisfiable if its 2-SAT subformula is satisfiable. That is, for p less than or equal to 2/5, random (2 + p)-SAT behaves like random 2-SAT. (C) 2001 Elsevier Science B.V. All rights reserved.