Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T07:08:10.717Z Has data issue: false hasContentIssue false
  • English
  • Français

Branching Process Approach for 2-Sat Thresholds

Part of: Decision theory Equilibrium statistical mechanics

Published online by Cambridge University Press:  14 July 2016

Elchanan Mossel  and
Arnab Sen
Elchanan Mossel*
Affiliation:
University of California, Berkeley
Arnab Sen*
Affiliation:
University of California, Berkeley
*
∗Postal address: Department of Statistics, University of California, Berkeley, CA 94720-3860, USA.
∗Postal address: Department of Statistics, University of California, Berkeley, CA 94720-3860, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

It is well known that, as n tends to ∞, the probability of satisfiability for a random 2-SAT formula on n variables, where each clause occurs independently with probability α / 2n, exhibits a sharp threshold at α = 1. We study a more general 2-SAT model in which each clause occurs independently but with probability αi / 2n, where i ∈ {0, 1, 2} is the number of positive literals in that clause. We generalize the branching process arguments used by Verhoeven (1999) to determine the satisfiability threshold for this model in terms of the maximum eigenvalue of the branching matrix.

Keywords

2-SATsatisfiabilityphase transitiontwo-type branching process

MSC classification

Secondary: 62C05: General considerations 82B26: Phase transitions (general)
Type
Research Article
Information
Journal of Applied Probability , Volume 47 , Issue 3 , September 2010 , pp. 796 - 810
Copyright
Copyright © Applied Probability Trust 2010 

Footnotes

Supported by NSF grants DMS 0528488 and DMS 0548249, and ONR grant N0014-07-1-05-06.

References

[1] Achlioptas, D. (2000). {Setting 2 variables at a time yields a new lower bound for random 3-{SAT} (extended abstract)}. In Proc. 32nd Annual ACM Symp. on Theory of Computing, Association for Computing Machinery, New York, pp. 28–37.Google Scholar
[2] Achlioptas, D. and Peres, Y. (2004). {The threshold for random k-{SAT} is 2k log 2-O(k)}. J. Amer. Math. Soc. 17, 947–973.Google Scholar
[3] Achlioptas, D. and Ricci-Tersenghi, F. (2006). {On the solution-space geometry of random constraint satisfaction problems}. In Proc. 38th Annual ACM Symp. Theory of Computing, Association for Computing Machinery, New York, pp. 130–139.Google Scholar
[4] Achlioptas, D. and Sorkin, G. B. (2000). {Optimal myopic algorithms for random 3-{SAT}}. In 41st Annual Symp. Foundations of Computer Science (Redondo Beach, CA, 2000), IEEE Computer Society Press, Los Alamitos, CA, pp. 590–600.Google Scholar
[5] Aldous, D. (2001). {The ζ(2) limit in the random assignment problem}. Random Structures Algorithms 18, 381–418.Google Scholar
[6] Aspvall, B., Plass, M. F. and Tarjan, R. E. (1979). {{A} linear-time algorithm for testing the truth of certain quantified Boolean formulas}. Inform. Process. Lett. 8, 121–123. (Correction: 14 (1982), 195.)CrossRefGoogle Scholar
[7] Bollobás, B. (2001). Random Graphs (Camb. Stud. Adv. Math. 73), 2nd edn. Cambridge University Press.CrossRefGoogle Scholar
[8] Bollobás, B. et al. (2001). {The scaling window of the 2-{SAT} transition}. Random Structures Algorithms 18, 201–256.CrossRefGoogle Scholar
[9] Chvátal, V. and Reed, B. (1992). {Mick gets some (the odds are on his side) (satisfiability)}. In Proc. 33rd Annual Symp. Foundations of Computer Science, IEEE Computer Society, Washington, DC, pp. 620–627.Google Scholar
[10] Cook, S. A. (1971). {The complexity of theorem-proving procedures}. In Proc. 3rd ACM Symp. Theory of Computing, Association for Computing Machinery, New York, pp. 151–158.Google Scholar
[11] Cooper, C., Frieze, A. and Sorkin, G. B. (2007). {Random 2-{SAT} with prescribed literal degrees}. Algorithmica 48, 249–265.Google Scholar
[12] D{ı´az, J., Kirousis, L., Mitsche, D. and Pérez-Giménez, X.} (2009). {On the satisfiability threshold of formulas with three literals per clause}. Theoret. Comput. Sci. 410, 2920–2934.Google Scholar
[13] Fernandez de la Vega, W. (1992). {On random 2-sat}. Unpublished manuscript.Google Scholar
[14] Fortuin, C. M., Kasteleyn, P. W. and Ginibre, J. (1971). {Correlation inequalities on some partially ordered sets}. Commun. Math. Phys. 22, 89–103.Google Scholar
[15] Friedgut, E. (1999). {Sharp thresholds of graph properties, and the k-sat problem}. J. Amer. Math. Soc. 12, 1017–1054.CrossRefGoogle Scholar
[16] Goerdt, A. (1992). {A threshold for unsatisfiability}. In Mathematical Foundations of Computer Science (Lecture Notes Comput. Sci. 629), Springer, Berlin, pp. 264–274.Google Scholar
[17] Goerdt, A. (1996). {A threshold for unsatisfiability}. J. Comput. System Sci. 53, 469–486.Google Scholar
[18] Harris, T. E. (2002). The Theory of Branching Processes. Dover Publications, Mineola, NY.Google Scholar
[19] Hatami, H. and Molloy, M. (2008). {Sharp thresholds for constraint satisfaction problems and homomorphisms}. Random Structures Algorithms 33, 310–332.Google Scholar
[20] Janson, S., Łuczak, T. and Rucinski, A. (2000). Random Graphs. Wiley-Interscience, New York.Google Scholar
[21] Kaporis, A. C., Kirousis, L. M. and Lalas, E. G. (2006). {The probabilistic analysis of a greedy satisfiability algorithm}. Random Structures Algorithms 28, 444–480.CrossRefGoogle Scholar
[22] Kesten, H. and Stigum, B. P. (1967). {Limit theorems for decomposable multi-dimensional Galton–Watson processes}. J. Math. Anal. Appl. 17, 309–338.Google Scholar
[23] Maneva, E., Mossel, E. and Wainwright, M. J. (2007). {{A new look at survey propagation and its generalizations}}. J. ACM 54, 41pp.CrossRefGoogle Scholar
[24] Mertens, S., Mézard, M. and Zecchina, R. (2006). {Threshold values of random K-{SAT} from the cavity method}. Random Structures Algorithms 28, 340–373.Google Scholar
[25] Mézard, M., Parisi, G. and Zecchina, R. (2002). {{Analytic and algorithmic solution of random satisfiability problems}}. Science 297, 812–815.Google Scholar
[26] Mossel, E., Weitz, D. and Wormald, N. (2009). {On the hardness of sampling independent sets beyond the tree threshold}. Prob. Theory Relat. Fields 143, 401–439.Google Scholar
[27] Verhoeven, Y. (1999). {{Random 2-SAT and unsatisfiability}}. Inform. Process. Lett. 72, 119–123.CrossRefGoogle Scholar
[28] Weitz, D. (2006). {Counting independent sets up to the tree threshold}. In Proc. 38th Annual ACM Symp. Theory of Computing, Association for Computing Machinery, New York, pp. 140–149.Google Scholar