The threshold for random -SAT is

Authors:
Dimitris Achlioptas and Yuval Peres

Journal:
J. Amer. Math. Soc. **17** (2004), 947-973

MSC (2000):
Primary 68R99, 82B26; Secondary 05C80

Published electronically:
August 27, 2004

MathSciNet review:
2083472

Full-text 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 126-127, 2002.**2.**A. Braunstein, M. Mézard, and R. Zecchina.

Survey propagation: an algorithm for satisfiability.

Preprint, 2002.**3.**Ming-Te Chao and John Franco,*Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the 𝑘-satisfiability problem*, Inform. Sci.**51**(1990), no. 3, 289–314. MR**1072035**, 10.1016/0020-0255(90)90030-E**4.**P. Cheeseman, B. Kanefsky, and W. Taylor.

Where the really hard problems are.

In*Proc. 12th International Joint Conference on Artificial Intelligence (IJCAI-91) Vol. 1*, pages 331-337, 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 620-627, 1992.**6.**N. G. de Bruijn,*Asymptotic methods in analysis*, 3rd ed., Dover Publications, Inc., New York, 1981. MR**671583****7.**Amir Dembo, Yuval Peres, Jay Rosen, and Ofer Zeitouni,*Thick points for planar Brownian motion and the Erdős-Taylor conjecture on random walk*, Acta Math.**186**(2001), no. 2, 239–270. MR**1846031**, 10.1007/BF02401841**8.**Amir Dembo and Ofer Zeitouni,*Large deviations techniques and applications*, 2nd ed., Applications of Mathematics (New York), vol. 38, Springer-Verlag, New York, 1998. MR**1619036****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**, 10.1006/jagm.1997.0867**10.**O. Dubois, Y. Boufkhad, and J. Mandler.

Typical random 3-SAT formulae and the satisfiability threshold.

In*Proc. 11th Annual Symposium on Discrete Algorithms*, pages 126-127, 2000.**11.**P. Erdős and L. Lovász,*Problems and results on 3-chromatic hypergraphs and some related questions*, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, North-Holland, Amsterdam, 1975, pp. 609–627. Colloq. Math. Soc. János Bolyai, Vol. 10. MR**0382050****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****13.**John Franco and Marvin Paull,*Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem*, Discrete Appl. Math.**5**(1983), no. 1, 77–87. MR**678818**, 10.1016/0166-218X(83)90017-3**14.**E. Friedgut.

Necessary and sufficient conditions for sharp thresholds of graph properties, and the -SAT problem.*J. Amer. Math. Soc.*, 12:1017-1054, 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**, 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 1-6, 2002.**17.**Svante Janson, Yannis C. Stamatiou, and Malvina Vamvakari,*Bounding the unsatisfiability threshold of random 3-SAT*, Random Structures Algorithms**17**(2000), no. 2, 103–116. MR**1774746**, 10.1002/1098-2418(200009)17:2<103::AID-RSA2>3.3.CO;2-G**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 574-585. 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**, 10.1002/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.3.CO;2-H**20.**M. Mézard, G. Parisi, and R. Zecchina.

Analytic and Algorithmic Solution of Random Satisfiability Problems.*Science*, 297: 812-815, 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 459-462, 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**, 10.1103/PhysRevE.56.1357**24.**I. Stewart.

Where drunkards hang out.*Nature*, News and Views, October 18, 2001.

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/S0894-0347-04-00464-3

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 DMS-0104073, NSF Grant DMS-0244479 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.