Rigorous results for random [formula omitted]-SAT

• Published in: Theoretical computer science 2001, Vol.265 (1), p.109-129
• Main Authors: Achlioptas, Dimitris, Kirousis, Lefteris M., Kranakis, Evangelos, Krizanc, Danny
• Format: Article
• Language: English
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/S0304-3975(01)00154-2

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 B k 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, F 2+p(n,m) , has m 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⩽2/5, with probability 1− o(1) , a random (2+p)-SAT formula is satisfiable iff its 2-SAT subformula is satisfiable. That is, for p⩽2/5, random (2+p)-SAT behaves like random 2-SAT.