research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:chita
TitleRigorous results for random (2 + p)-SAT
Bibtex cite IDRACTI-RU1-2001-2
Journal Theoretical Computer Science (TCS)
Year published 2001
Volume 265
Pages 109-129
In recent years there has been signi1cant interest in the study of random k-SAT formulae. For a given set of n Boolean variables, let Bk denote the set of all possible disjunctions of k distinct, non-complementary literals from its variables (k-clauses). A random k-SAT formula Fk (n;m) is formed by selectinguniformly and independently m clauses from Bk and takingtheir 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 (1 − p)m from B2. Usingthe 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 1rst rigorous results for random (2 + p)-SAT, includingthe followingsurprisingfact: for p 6 2=5, with probability 1 − o(1), a random (2 + p)-SAT formula is satis1able i@ its 2-SAT subformula is satis1able. That is, for p 6 2=5, random (2 + p)-SAT behaves like random 2-SAT.
Achlioptas, Dimitris
Kirousis, Lefteris
Kranakis, Evangelos
Krizanc, Danny
j12.pdf (main file)
Publication ID186