The threshold for random SAT is
Authors:
Dimitris Achlioptas and Yuval Peres
Journal:
J. Amer. Math. Soc. 17 (2004), 947973
MSC (2000):
Primary 68R99, 82B26; Secondary 05C80
Published electronically:
August 27, 2004
MathSciNet review:
2083472
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Let be a random CNF formula formed by selecting uniformly and independently out of all possible clauses on variables. It is well known that if , then is unsatisfiable with probability that tends to 1 as . We prove that if , where , then is satisfiable with probability that tends to 1 as . Our technique, in fact, yields an explicit lower bound for the random SAT threshold for every . For our bounds improve all previously known such bounds.
 1.
D. Achlioptas and C. Moore.
The asymptotic order of the random SAT threshold. In Proc. 43rd Annual Symposium on Foundations of Computer Science, pages 126127, 2002.
 2.
A. Braunstein, M. Mézard, and R. Zecchina.
Survey propagation: an algorithm for satisfiability. Preprint, 2002.
 3.
MingTe
Chao and John
Franco, Probabilistic analysis of a generalization of the
unitclause literal selection heuristics for the 𝑘satisfiability
problem, Inform. Sci. 51 (1990), no. 3,
289–314. MR 1072035
(91g:68076), http://dx.doi.org/10.1016/00200255(90)90030E
 4.
P. Cheeseman, B. Kanefsky, and W. Taylor.
Where the really hard problems are. In Proc. 12th International Joint Conference on Artificial Intelligence (IJCAI91) Vol. 1, pages 331337, 1991.
 5.
V. Chvátal and B. Reed.
Mick gets some (the odds are on his side). In Proc. 33rd Annual Symposium on Foundations of Computer Science, pages 620627, 1992.
 6.
N.
G. de Bruijn, Asymptotic methods in analysis, 3rd ed., Dover
Publications, Inc., New York, 1981. MR 671583
(83m:41028)
 7.
Amir
Dembo, Yuval
Peres, Jay
Rosen, and Ofer
Zeitouni, Thick points for planar Brownian motion and the
ErdősTaylor conjecture on random walk, Acta Math.
186 (2001), no. 2, 239–270. MR 1846031
(2002k:60106), http://dx.doi.org/10.1007/BF02401841
 8.
Amir
Dembo and Ofer
Zeitouni, Large deviations techniques and applications, 2nd
ed., Applications of Mathematics (New York), vol. 38, SpringerVerlag,
New York, 1998. MR 1619036
(99d:60030)
 9.
O.
Dubois and Y.
Boufkhad, A general upper bound for the satisfiability threshold of
random 𝑟SAT formulae, J. Algorithms 24
(1997), no. 2, 395–420. MR 1469655
(98e:68103), http://dx.doi.org/10.1006/jagm.1997.0867
 10.
O. Dubois, Y. Boufkhad, and J. Mandler.
Typical random 3SAT formulae and the satisfiability threshold. In Proc. 11th Annual Symposium on Discrete Algorithms, pages 126127, 2000.
 11.
P.
Erdős and L.
Lovász, Problems and results on 3chromatic hypergraphs and
some related questions, Infinite and finite sets (Colloq., Keszthely,
1973; dedicated to P. Erdős on his 60th birthday), Vol. II,
NorthHolland, Amsterdam, 1975, pp. 609–627. Colloq. Math. Soc.
János Bolyai, Vol. 10. MR 0382050
(52 #2938)
 12.
P.
Erdős and S.
J. Taylor, Some problems concerning the structure of random walk
paths, Acta Math. Acad. Sci. Hungar. 11 (1960),
137–162. (unbound insert) (English, with Russian summary). MR 0121870
(22 #12599)
 13.
John
Franco and Marvin
Paull, Probabilistic analysis of the DavisPutnam procedure for
solving the satisfiability problem, Discrete Appl. Math.
5 (1983), no. 1, 77–87. MR 678818
(84e:68038), http://dx.doi.org/10.1016/0166218X(83)900173
 14.
E. Friedgut.
Necessary and sufficient conditions for sharp thresholds of graph properties, and the SAT problem. J. Amer. Math. Soc., 12:10171054, 1999.
 15.
Alan
Frieze and Stephen
Suen, Analysis of two simple heuristics on a random instance of
𝑘SAT, J. Algorithms 20 (1996), no. 2,
312–355. MR 1379227
(97c:68062), http://dx.doi.org/10.1006/jagm.1996.0016
 16.
A. Frieze and N. C. Wormald.
Random SAT: a tight threshold for moderately growing . In Proc. 5th International Symposium on Theory and Applications of Satisfiability Testing, pages 16, 2002.
 17.
Svante
Janson, Yannis
C. Stamatiou, and Malvina
Vamvakari, Bounding the unsatisfiability threshold of random
3SAT, Random Structures Algorithms 17 (2000),
no. 2, 103–116. MR 1774746
(2001c:68065), http://dx.doi.org/10.1002/10982418(200009)17:2<103::AIDRSA2>3.3.CO;2G
 18.
A. Kaporis, L. M. Kirousis, and E. G. Lalas.
The probabilistic analysis of a greedy satisfiability algorithm. In Proc. 10th Annual European Symposium on Algorithms, volume 2461 of Lecture Notes in Computer Science, pages 574585. Springer, 2002.
 19.
Lefteris
M. Kirousis, Evangelos
Kranakis, Danny
Krizanc, and Yannis
C. Stamatiou, Approximating the unsatisfiability threshold of
random formulas, Random Structures Algorithms 12
(1998), no. 3, 253–269. MR 1635256
(2000c:68069), http://dx.doi.org/10.1002/(SICI)10982418(199805)12:3<253::AIDRSA3>3.3.CO;2H
 20.
M. Mézard, G. Parisi, and R. Zecchina.
Analytic and Algorithmic Solution of Random Satisfiability Problems. Science, 297: 812815, 2002.
 21.
M. Mézard and R. Zecchina.
Random satisfiability: from an analytic solution to a new efficient algorithm. Phys. Rev. E, 66, 056126, 2002.
 22.
D. G. Mitchell, B. Selman, and H. J. Levesque.
Hard and easy distributions of SAT problems. In Proc. 10th National Conference on Artificial Intelligence, pages 459462, 1992.
 23.
Rémi
Monasson and Riccardo
Zecchina, Statistical mechanics of the random
𝐾satisfiability model, Phys. Rev. E (3) 56
(1997), no. 2, 1357–1370. MR 1464158
(98g:82022), http://dx.doi.org/10.1103/PhysRevE.56.1357
 24.
I. Stewart.
Where drunkards hang out. Nature, News and Views, October 18, 2001.
 1.
 D. Achlioptas and C. Moore.
The asymptotic order of the random SAT threshold. In Proc. 43rd Annual Symposium on Foundations of Computer Science, pages 126127, 2002.
 2.
 A. Braunstein, M. Mézard, and R. Zecchina.
Survey propagation: an algorithm for satisfiability. Preprint, 2002.
 3.
 M.T. Chao and J. Franco.
Probabilistic analysis of a generalization of the unitclause literal selection heuristics for the satisfiability problem. Inform. Sci., 51(3):289314, 1990. MR 1072035 (91g:68076)
 4.
 P. Cheeseman, B. Kanefsky, and W. Taylor.
Where the really hard problems are. In Proc. 12th International Joint Conference on Artificial Intelligence (IJCAI91) Vol. 1, pages 331337, 1991.
 5.
 V. Chvátal and B. Reed.
Mick gets some (the odds are on his side). In Proc. 33rd Annual Symposium on Foundations of Computer Science, pages 620627, 1992.
 6.
 N. G. de Bruijn.
Asymptotic methods in analysis. Dover Publications Inc., New York, 3rd edition, 1981. MR 0671583 (83m:41028)
 7.
 A. Dembo, Y. Peres, J. Rosen and O. Zeitouni.
Thick points for planar Brownian motion and the ErdosTaylor conjecture on random walk. Acta Math., 186:239270, 2001. MR 1846031 (2002k:60106)
 8.
 A. Dembo and O. Zeitouni.
Large deviations techniques and applications. Springer Verlag, New York, 2nd edition, 1998. MR 1619036 (99d:60030)
 9.
 O. Dubois and Y. Boufkhad.
A general upper bound for the satisfiability threshold of random SAT formulae. J. Algorithms, 24(2):395420, 1997. MR 1469655 (98e:68103)
 10.
 O. Dubois, Y. Boufkhad, and J. Mandler.
Typical random 3SAT formulae and the satisfiability threshold. In Proc. 11th Annual Symposium on Discrete Algorithms, pages 126127, 2000.
 11.
 P. Erdos and L. Lovász.
Problems and results on chromatic hypergraphs and some related questions. Colloq. Math. Soc. János Bolyai, Vol. 10, 609627. MR 0382050 (52:2938)
 12.
 P. Erdos and S. J. Taylor.
Some problems concerning the structure of random walk paths. Acta Sci. Hung. 11:137162, 1960. MR 0121870 (22:12599)
 13.
 J. Franco and M. Paull.
Probabilistic analysis of the DavisPutnam procedure for solving the satisfiability problem. Discrete Appl. Math., 5(1):7787, 1983. MR 0678818 (84e:68038)
 14.
 E. Friedgut.
Necessary and sufficient conditions for sharp thresholds of graph properties, and the SAT problem. J. Amer. Math. Soc., 12:10171054, 1999.
 15.
 A. M. Frieze and S. Suen.
Analysis of two simple heuristics on a random instance of SAT. J. Algorithms, 20(2):312355, 1996. MR 1379227 (97c:68062)
 16.
 A. Frieze and N. C. Wormald.
Random SAT: a tight threshold for moderately growing . In Proc. 5th International Symposium on Theory and Applications of Satisfiability Testing, pages 16, 2002.
 17.
 S. Janson, Y. C. Stamatiou, and M. Vamvakari.
Bounding the unsatisfiability threshold of random 3SAT. Random Structures Algorithms, 17(2):103116, 2000. MR 1774746 (2001c:68065)
 18.
 A. Kaporis, L. M. Kirousis, and E. G. Lalas.
The probabilistic analysis of a greedy satisfiability algorithm. In Proc. 10th Annual European Symposium on Algorithms, volume 2461 of Lecture Notes in Computer Science, pages 574585. Springer, 2002.
 19.
 L. M. Kirousis, E. Kranakis, D. Krizanc, and Y. Stamatiou.
Approximating the unsatisfiability threshold of random formulas. Random Structures Algorithms, 12(3):253269, 1998. MR 1635256 (2000c:68069)
 20.
 M. Mézard, G. Parisi, and R. Zecchina.
Analytic and Algorithmic Solution of Random Satisfiability Problems. Science, 297: 812815, 2002.
 21.
 M. Mézard and R. Zecchina.
Random satisfiability: from an analytic solution to a new efficient algorithm. Phys. Rev. E, 66, 056126, 2002.
 22.
 D. G. Mitchell, B. Selman, and H. J. Levesque.
Hard and easy distributions of SAT problems. In Proc. 10th National Conference on Artificial Intelligence, pages 459462, 1992.
 23.
 R. Monasson and R. Zecchina.
Statistical mechanics of the random satisfiability model. Phys. Rev. E (3), 56(2):13571370, 1997. MR 1464158 (98g:82022)
 24.
 I. Stewart.
Where drunkards hang out. Nature, News and Views, October 18, 2001.
Similar Articles
Retrieve articles in Journal of the American Mathematical Society
with MSC (2000):
68R99,
82B26,
05C80
Retrieve articles in all journals
with MSC (2000):
68R99,
82B26,
05C80
Additional Information
Dimitris Achlioptas
Affiliation:
Microsoft Research, One Microsoft Way, Redmond, Washington 98052
Email:
optas@microsoft.com
Yuval Peres
Affiliation:
Department of Statistics, University of California, Berkeley, California 94720
Email:
peres@stat.berkeley.edu
DOI:
http://dx.doi.org/10.1090/S0894034704004643
PII:
S 08940347(04)004643
Keywords:
Satisfiability,
random formulas,
phase transitions
Received by editor(s):
September 4, 2003
Published electronically:
August 27, 2004
Additional Notes:
This research was supported by NSF Grant DMS0104073, NSF Grant DMS0244479 and a Miller Professorship at UC Berkeley. Part of this work was done while visiting Microsoft Research.
Article copyright:
© Copyright 2004
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
