20010903
Rigorous results for random (2+p)SAT
Publication
Publication
Theoretical Computer Science , Volume 265  Issue 12 p. 109 129
In recent years there has been significant interest in the study of random kSAT formulae. For a given set of n Boolean variables, let Bk denote the set of all possible disjunctions of k distinct, noncomplementary literals from its variables (kclauses). A random kSAT formula Fk(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∈[0,1], a random (2+p)SAT formula, F2+p(n,m), has m randomly chosen clauses over n variables, where pm clauses are chosen from B3 and (1p)m from B2. Using the heuristic "replica method" of statistical mechanics, Monasson and Zecchina gave a number of nonrigorous 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≤2/5, with probability 1o(1), a random (2+p)SAT formula is satisfiable iff its 2SAT subformula is satisfiable. That is, for p≤2/5, random (2+p)SAT behaves like random 2SAT.
Additional Metadata  

dx.doi.org/10.1016/S03043975(01)001542  
Theoretical Computer Science  
Organisation  School of Computer Science 
Achlioptas, D. (Dimitris), Kirousis, L.M. (Lefteris M.), Kranakis, E, & Krizanc, D. (Danny). (2001). Rigorous results for random (2+p)SAT. Theoretical Computer Science, 265(12), 109–129. doi:10.1016/S03043975(01)001542
