×

zbMATH — the first resource for mathematics

The scaling window of the 2-SAT transition. (English) Zbl 0979.68053
Summary: We consider the random 2-SATisfiability (2-SAT) problem, in which each instance is a formula that is the conjunction of \(m\) clauses of the form \(x\vee y\), chosen uniformly at random from among all 2-clauses on \(n\) Boolean variables and their negations. As \(m\) and \(n\) tend to infinity in the ratio \(m/m\to\alpha\), the problem is known to have a phase transition at \(\alpha_c=1\), below which the probability that the formula is satisfiable tends to one and above which it tends to zero. We determine the finite-size scaling about this transition, namely the scaling of the maximal window \(W(n,\delta)= (\alpha_-(n, \delta), \alpha_+(n,\delta))\) such that the probability of satisfiability is greater than \(1-\delta\) for \(\alpha< \alpha_-\) and is less than \(\delta\) for \(\alpha> \alpha_+\). We show that \(W(n, \delta)= (1-\Theta(n^{-1/3})\), \(1+ \Theta(n^{-1/3}))\), where the constants implicit in \(\Theta\) depend on \(\delta\). We also determine the rates at which the probability of satisfiability approaches one and zero at the boundaries of the window. Namely, for \(m= (1+\varepsilon)n\), where \(\varepsilon\) may depend on \(n\) as long as \(|\varepsilon|\) is sufficiently small and \(\varepsilon n|n^{1/3}\) is sufficiently large, we show that the probability of satisfiability decays like \(\exp(-\Theta(n\varepsilon^3))\) above the window, and goes to one like \(1-\Theta(n^{- 1}|\varepsilon|^{- 3})\) below the window. We prove these results by defining an order parameter for the transition and establishing its scaling behavior in \(n\) both inside an outside the window. Using this order parameter, we prove that the 2-SAT phase transition is continuous with an order parameter critical exponent of 1. We also determine the values of two other critical exponents, showing that the exponents of 2-SAT are identical to those of the random graph.

MSC:
68Q25 Analysis of algorithms and problem complexity
05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] D. Achlioptas Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract) 28 37
[2] Aldous., A random walk construction of uniform spanning trees and uniform labelled trees, SIAM J Discrete Math 3 pp 450– (1990) · Zbl 0717.05028 · doi:10.1137/0403039
[3] D. Achlioptas M. Molloy personal communication
[4] Aspvall, A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Inform Process Lett 8 pp 121– (1979) · Zbl 0398.68042 · doi:10.1016/0020-0190(79)90002-4
[5] Alon, The Probabilistic Method (1992)
[6] D. Achlioptas G.B. Sorkin Optimal myopic algorithms for random 3-SAT 590 600
[7] B. Bollobás C. Borgs J.T. Chayes J.H. Kim Lecture at the Workshop on the Interface between Statistical Physics and Computer Science, Torino, Italy
[8] B. Bollobás C. Borgs J.T. Chayes J.H. Kim D.B. Wilson Critical exponents of the 2-SAT transition
[9] Borgs, Uniform boundedness of critical crossing probabilities implies hyperscaling, Random Structures Algorithms · Zbl 0940.60089
[10] C. Borgs J.T. Chayes H. Kesten J. Spencer Birth of the infinite cluster: Finite-size scaling in percolation · Zbl 1038.82035
[11] Bender, The asymptotic number of labeled connected graphs with a given number of vertices and edges, Random Structures Algorithms 1 pp 127– (1990) · Zbl 0745.05022 · doi:10.1002/rsa.3240010202
[12] A. Broder A. Frieze E. Upfal On the satisfiability and maximum satisfiablity of random 3-CNF formulas 322 330
[13] Bollobás, The evolution of random graphs, Trans Amer Math Soc 286 pp 257– (1984) · Zbl 0579.05046 · doi:10.2307/1999405
[14] Bollobás., Random Graphs (1985)
[15] Britikov, On the random graph structure near the critical point, Discrete Math. Appl. 1 pp 301– (1991) · Zbl 0746.05054 · doi:10.1515/dma.1991.1.3.301
[16] J.M. Crawford L.D. Auton Experimental results on the crossover point in satisfiability problems 21 27
[17] Chao, Probabilistic analysis of two heuristics for the 3-satisfiability problem, SIAM J Comput 5 pp 1106– (1986) · Zbl 0621.68031 · doi:10.1137/0215080
[18] Chao, Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiable problem, Inform Sci 51 pp 289– (1990) · Zbl 0706.68053 · doi:10.1016/0020-0255(90)90030-E
[19] J.T. Chayes Finite-size scaling in percolation 113 22
[20] Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann Math Stat 23 pp 493– (1952) · Zbl 0048.11804 · doi:10.1214/aoms/1177729330
[21] S.A. Cook The complexity of theorem-proving procedures 151 158
[22] J.T. Chayes A. Puha T. Sweet Independent and dependent percolation, Probability theory and applications IAS Park City Math Ser 6 Amer Math Soc Providence, RI 1999 49 166
[23] V. Chvátal B. Reed Mick gets some (the odds are on his side) 620 627 · Zbl 0977.68538
[24] Chvátal, Many hard examples for resolution, JACM 35 pp 759– (1988) · Zbl 0712.03008 · doi:10.1145/48014.48016
[25] Dubois, A general upper bound for the satisfiablity threshold of random k-SAT formulas, J Algorithms 24 pp 395– (1997) · Zbl 0883.68065 · doi:10.1006/jagm.1997.0867
[26] O. Dubois Y. Boufkhad J. Mandler Typical random 3-SAT formulae and the satisfiability threshold 126 127 · Zbl 0959.68135
[27] Dubois, Counting the number of solutions for instances of satisfiability, Theoret Comput Sci 81 pp 49– (1991) · Zbl 0725.68045 · doi:10.1016/0304-3975(91)90315-S
[28] El Maftouhi, On random 3-sat, Combin Probab Comput 4 pp 189– (1995) · Zbl 0840.68051 · doi:10.1017/S0963548300001590
[29] Erdos, On the evolution of random graphs, Magyar Tud Akad Mat Kutató Int Közl 5 pp 17– (1960)
[30] Erdos, On the evolution of random graphs, Bull Inst Internat Statist 38 pp 343– (1961)
[31] Friedgut, Sharp thresholds of graph properties, and the k-sat problem, J Amer Math Soc 12 pp 1017– (1999) · Zbl 0932.05084 · doi:10.1090/S0894-0347-99-00305-7
[32] Feller, An Introduction to Probability Theory and Its Applications I (1968) · Zbl 0155.23101
[33] W. Fernandez de la Vega On random 2-SAT
[34] W. Fernandez de la Vega On random 2-SAT
[35] Fortuin, Correlation inequalities on some partially ordered sets, Commun Math Phys 22 pp 89– (1971) · Zbl 0346.06011 · doi:10.1007/BF01651330
[36] Franco, Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem, Discrete Applied Mathematics 5 pp 77– (1983) · Zbl 0497.68021 · doi:10.1016/0166-218X(83)90017-3
[37] Frieze, Analysis of two simple heuristics for a random instance of K-SAT, J Algorithms 20 pp 312– (1996) · Zbl 0852.68038 · doi:10.1006/jagm.1996.0016
[38] Garey, Computers and Intractability: A Guide to the Theory of NP-Completeness (1979)
[39] Garey, Some simplified NP-complete graph problems, Theoret Comput Sci 1 pp 237– (1976) · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1
[40] Goerdt, Lecture Notes in Computer Science 629, in: Mathematical Foundations of Computer Science, 17th Intl Symposium pp 264– (1992) · doi:10.1007/3-540-55808-X_25
[41] Goerdt, A threshold for unsatisfiability, J Compute System Sci 53 pp 469– (1996) · Zbl 0870.68077 · doi:10.1006/jcss.1996.0081
[42] Goerdt, A remark on random 2-SAT, Discrete Appl Math 96-97 pp 107– (1999) · Zbl 0937.68148 · doi:10.1016/S0166-218X(99)00034-7
[43] Harris, A lower bound for the critical probability in certain percolation processes, Proc Camb Philos Soc 56 pp 13– (1960) · Zbl 0122.36403 · doi:10.1017/S0305004100034241
[44] J. Håstad Some optimal in-approximability results 1 10
[45] Janson, Bounding the unsatisfiability threshold of random 3-SAT, Random Structures Algorithms 17 pp 103– (2000) · Zbl 0958.03028 · doi:10.1002/1098-2418(200009)17:2<103::AID-RSA2>3.0.CO;2-P
[46] Janson, The birth of the giant component, Random Structures Algorithms 4 pp 231– (1994)
[47] Karp., The transitive closure of a random digraph, Random Structures Algorithms 1 pp 73– (1990) · Zbl 0712.68076 · doi:10.1002/rsa.3240010106
[48] L. Kirousis E. Kranakis D. Krizanc Approximating the unsatisfiability threshold of random formulas 27 38 · Zbl 0936.68038
[49] Kleitman, Families of non-disjoint subsets, J Combin Theory 1 pp 153– (1966) · Zbl 0141.00801 · doi:10.1016/S0021-9800(66)80012-1
[50] Kamath, Tail bounds for occupancy and the satisfiability threshold conjecture, Random Structures Algorithms 7 pp 59– (1995) · Zbl 0834.68051 · doi:10.1002/rsa.3240070105
[51] Kirkpatrick, Critical behavior in the satisfiability of random Boolean expressions, Science 264 pp 1297– (1994) · Zbl 1226.68097 · doi:10.1126/science.264.5163.1297
[52] Łuczak, The structure of a random graph at the point of the phase trasnsition, Trans Amer Math Soc 341 pp 721– (1994) · doi:10.1090/S0002-9947-1994-1138950-5
[53] T. Larrabee Y. Tsuji Evidence for satisfiability threshold for random 3CNF formulas 112
[54] Łuczak, Component behavior near the critical point of the random graph process, Random Structures Algorithms 1 pp 287– (1990) · Zbl 0745.05048 · doi:10.1002/rsa.3240010305
[55] McDiarmid, On the method of bounded differences, Surveys in Combinatorics pp 148– (1989) · Zbl 0712.05012
[56] Mézard, Spin Glass Theory and Beyond (1987)
[57] D. Mitchell B. Selman H. Levesque Hard and easy distributions of SAT problems 459 465
[58] Monasson, The entropy of the K-satisfiability problem, Phys Rev Lett 76 pp 3881– (1996) · Zbl 1042.82567 · doi:10.1103/PhysRevLett.76.3881
[59] Monasson, Statistical mechanics of the random K-SAT model, Phys Rev E 56 pp 1357– (1997) · doi:10.1103/PhysRevE.56.1357
[60] Monasson, 2+-SAT: Relation of typical-case complexity to the nature of the phase transition, Random Structures Algorithms 15 pp 414– (1999) · Zbl 0931.68056 · doi:10.1002/(SICI)1098-2418(199910/12)15:3/4<414::AID-RSA10>3.0.CO;2-G
[61] Selman, Critical behavior in the computational cost of satisfiability testing, Artificial Intelligence 81 pp 273– (1996) · doi:10.1016/0004-3702(95)00056-9
[62] Verhoeven, Random 2-SAT and unsatisfiability, Inf Process Lett 72 pp 119– (1999) · Zbl 0999.68086 · doi:10.1016/S0020-0190(99)00128-3
[63] D.B. Wilson http://dbwilson.com/2sat-data/ 1998
[64] D.B. Wilson The empirical values of the critical k-SAT exponents are wrong 2000
[65] Wright, The number of connected sparsely edged graphs, J Graph Theory 1 pp 317– (1977) · Zbl 0337.05119 · doi:10.1002/jgt.3190010407
[66] Wright, The number of connected sparsely edged graphs III. Asymptotic results, J Graph Theory 4 pp 393– (1980) · Zbl 0416.05048 · doi:10.1002/jgt.3190040409
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.