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

DOI:
https://doi.org/10.1090/S0894-0347-04-00464-3

Published electronically:
August 27, 2004

MathSciNet review:
2083472

Full-text PDF

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.**M.-T. Chao and J. Franco.

Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the -satisfiability problem.*Inform. Sci.*, 51(3):289-314, 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 (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*.

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 Erdos-Taylor conjecture on random walk.*Acta Math.*, 186:239-270, 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):395-420, 1997. MR**1469655 (98e:68103)****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. Erdos and L. Lovász.

Problems and results on -chromatic hypergraphs and some related questions.

Colloq. Math. Soc. János Bolyai, Vol. 10, 609-627. MR**0382050 (52:2938)****12.**P. Erdos and S. J. Taylor.

Some problems concerning the structure of random walk paths.*Acta Sci. Hung.*11:137-162, 1960. MR**0121870 (22:12599)****13.**J. Franco and M. Paull.

Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem.*Discrete Appl. Math.*, 5(1):77-87, 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:1017-1054, 1999.**15.**A. M. Frieze and S. Suen.

Analysis of two simple heuristics on a random instance of -SAT.*J. Algorithms*, 20(2):312-355, 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 1-6, 2002.**17.**S. Janson, Y. C. Stamatiou, and M. Vamvakari.

Bounding the unsatisfiability threshold of random 3-SAT.*Random Structures Algorithms*, 17(2):103-116, 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 574-585. 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):253-269, 1998. MR**1635256 (2000c:68069)****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. Monasson and R. Zecchina.

Statistical mechanics of the random -satisfiability model.*Phys. Rev. E (3)*, 56(2):1357-1370, 1997. MR**1464158 (98g:82022)****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:
https://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.