Read wilsonbollobas-ref.pdf text version






From References: 26 From Reviews: 2

MR1824274 (2002a:68052) 68Q25 Bollob´ s, B´ la (1-MEMP); Borgs, Christian (1-MSFT); Chayes, Jennifer T. (1-MSFT); a e Kim, Jeong Han (1-MSFT); Wilson, David B. [Wilson, David Bruce] (1-MSFT) The scaling window of the 2-SAT transition. (English summary) Random Structures Algorithms 18 (2001), no. 3, 201­256. 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 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/n , the problem is known to have a phase transition at 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, ) = (- (n, ), + (n, )) such that the probability of satisfiability is greater than 1 - for < - and is less than for > + . We show that W (n, ) = (1 - (n-1/3 ), 1 + (n-1/3 )), where the constants implicit in depend on . 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 + )n, where may depend on n as long as || is sufficiently small and ||n1/3 is sufficiently large, we show that the probability of satisfiability decays like exp(-(n3 )) above the window, and goes to one like 1 - (n-1 ||-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 and 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." References 1. D. Achlioptas, Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract), Proc. 32nd ACM Symposium on Theory of Computing, (2000), pp. 28­ 37. MR2114514 2. D. J. Aldous. A random walk construction of uniform spanning trees and uniform labelled trees, SIAM J Discrete Math, 3 (1990), 450­465. MR1069105 (91h:60013) 3. D. Achlioptas and M. Molloy, personal communication (1998). 4. B. Aspvall, M. F. Plass, and R. E. Tarjan, A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Inform Process Lett 8 (1979), 121­123. MR0526451 (80b:68050) 5. N. Alon and J. Spencer. The Probabilistic Method, John Wiley & Sons, New York 1992. MR1140703 (93h:60002) 6. D. Achlioptas and G. B. Sorkin, Optimal myopic algorithms for random 3-SAT, Proc. 41st Symp the Foundations of Computer Science, 2000, pp. 590­600. MR1931856 7. B. Bollob´ s, C. Borgs, J. T. Chayes, and J. H. Kim, Lecture at the Workshop on the Interface a between Statistical Physics and Computer Science, Torino, Italy, (1998) unpublished.

8. B. Bollob´ s, C. Borgs, J. T. Chayes, J. H. Kim, and D. B. Wilson, Critical exponents of the a 2-SAT transition, in preparation (2000). 9. C. Borgs, J. T. Chayes, H. Kesten, and J. Spencer, Uniform boundedness of critical crossing probabilities implies hyperscaling, Random Structures Algorithms (to appear). cf. MR 2001a:60111 10. C. Borgs, J. T. Chayes, H. Kesten, and J. Spencer, Birth of the infinite cluster: Finite-size scaling in percolation, preprint (1998). cf. MR 2002k:60199 11. E. A. Bender, E. R. Canfield and B. D. McKay, The asymptotic number of labeled connected graphs with a given number of vertices and edges, Random Structures Algorithms 1 (1990), 127­169. MR1138421 (92i:05108) 12. A. Broder, A. Frieze, and E. Upfal, On the satisfiability and maximum satisfiablity of random 3-CNF formulas, Proc 4th ACM-SIAM Symp Discrete Algorithms, 1993, pp. 322­330. MR1213244 (94b:03023) 13. B. Bollob´ s, The evolution of random graphs, Trans Amer Math Soc 286 (1984), 257­274. a MR0756039 (85k:05090) 14. B. Bollob´ s. Random Graphs, Academic Press, London, 1985. MR0809996 (87f:05152) a 15. V. E. Britikov, On the random graph structure near the critical point, Discrete Math. Appl., 1 (1991), 301­309 [Diskret Mat 1 (1989), 121­128]. MR1044244 (91c:05162) 16. J. M. Crawford and L. D. Auton, Experimental results on the crossover point in satisfiability problems, Proc. 11th Natl Conf Artificial Intelligence, 1993 21­27. 17. M. T. Chao and J. Franco, Probabilistic analysis of two heuristics for the 3-satisfiability problem, SIAM J Comput 5 (1986), 1106­1118. MR0861375 (88b:68079) 18. M. T. Chao and J. Franco, Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiable problem, Inform Sci 51 (1990), 289­314. MR1072035 (91g:68076) 19. J. T. Chayes, Finite-size scaling in percolation, Proc Intl Congress of Mathematicians, Vol. III (Berlin, 1998), Doc Math Extra Vol. III (1998), 113­122. MR1648146 (99k:60245) 20. H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann Math Stat 23 (1952), 493­507. MR0057518 (15,241c) 21. S. A. Cook, The complexity of theorem-proving procedures Proc. 3rd ACM Symp Theory of Computing, 1971 pp. 151­158. 22. J. T. Chayes, A. Puha, and T. Sweet, Independent and dependent percolation, Probability theory and applications (Princeton, NJ, 1996), in IAS/Park City Math Ser Vol 6, Amer Math Soc, Providence, RI 1999, pp. 49­166. MR1678308 (2000f:60147) 23. V. Chv´ tal and B. Reed, Mick gets some (the odds are on his side), Proc. 33rd Symp Foundations a of Computer Science, 1992, pp. 620­627. 24. V. Chv´ tal and E. Szemer´ di, Many hard examples for resolution, JACM 35 (1988), 759­768. a e MR1072398 (91f:68182) 25. O. Dubois and Y. Boufkhad, A general upper bound for the satisfiablity threshold of random k-SAT formulas, J Algorithms 24 (1997), 395­420. MR1469655 (98e:68103) 26. O. Dubois, Y. Boufkhad, and J. Mandler, Typical random 3-SAT formulae and the satisfiability threshold, Research announcement at ICTP, Sept 1999; Two-page abstract appears in Proc 11th

27. 28. 29. 30. 31. 32. 33. 34. 35. 36.

37. 38. 39. 40.

41. 42. 43. 44. 45. 46.

ACM-SIAM Symp on Discrete Algorithms, 2000, pp. 126­127. O. Dubois, Counting the number of solutions for instances of satisfiability, Theoret Comput Sci 81 (1991), 49­64. MR1103098 (93d:68031) A. El Maftouhi and W. Fernandez de la Vega, On random 3-sat, Combin Probab Comput 4 (1995), 189­195. MR1356574 (96f:03007) P. Erd s and A. R´ nyi, On the evolution of random graphs, Magyar Tud Akad Mat Kutat´ Int o e o K¨ zl 5 (1960), 17­61. MR0125031 (23 #A2338) o P. Erd s and A. R´ nyi, On the evolution of random graphs, Bull Inst Internat Statist 38 (1961), o e 343­347. MR0148055 (26 #5564) E. Friedgut, with appendix by J. Bourgain, Sharp thresholds of graph properties, and the k-sat problem, J Amer Math Soc 12 (1999), 1017­1054. MR1678031 (2000a:05183) W. Feller, An Introduction to Probability Theory and Its Applications, Volume I, 3rd Ed., John Wiley & Sons, London, 1968. MR0228020 (37 #3604) W. Fernandez de la Vega, On random 2-SAT, unpublished manuscript (1992). W. Fernandez de la Vega, On random 2-SAT (revised version), preprint (1998). cf. MR 89g:05094 C. M. Fortuin, P. W. Kasteleyn, and J. Ginibre, Correlation inequalities on some partially ordered sets, Commun Math Phys 22 (1971), 89­103. MR0309498 (46 #8607) J. Franco and M. Paul, Probabilistic analysis of the Davis--Putnam procedure for solving the satisfiability problem, Discrete Applied Mathematics 5 (1983), 77­87. MR0678818 (84e:68038) A. Frieze and S. Suen, Analysis of two simple heuristics for a random instance of K-SAT, J Algorithms 20 (1996), 312­335. MR1379227 (97c:68062) M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, 1979. MR0519066 (80g:68056) M. R. Garey, D. S. Johnson, and L. Stockmeyer, Some simplified NP-complete graph problems, Theoret Comput Sci 1 (1976), 237­267. MR0411240 (53 #14978) A. Goerdt, A threshold for unsatisfiability, Mathematical Foundations of Computer Science, 17th Intl Symposium, I.M. Havel and V. Koubek, Eds., Lecture Notes in Computer Science No. 629, Springer Verlag, Berlin (1992), 264­274. MR1255142 (94j:03011) A. Goerdt, A threshold for unsatisfiability, J Compute System Sci 53 (1996), 469­486. MR1423858 (98i:03012) A. Goerdt, A remark on random 2-SAT, Discrete Appl Math 96­97 (1999), 107­110. MR1724718 (2000h:03018) T. E. Harris, A lower bound for the critical probability in certain percolation processes, Proc Camb Philos Soc 56 (1960), 13­20. MR0115221 (22 #6023) J. H° stad, Some optimal in-approximability results, Proc 29th ACM Symp Theory of Compua tation, 1997, pp. 1­10. MR1715618 S. Janson, Y. C. Stamatiou, and M. Vamvakari, Bounding the unsatisfiability threshold of random 3-SAT, Random Structures Algorithms 17 (2000), 103­116. MR1774746 (2001c:68065) S. Janson, D. Knuth, T. Luczak, and B. Pittel, The birth of the giant component, Random Structures Algorithms 4 (1994), 231­358. MR1220220 (94h:05070)

47. R. M. Karp. The transitive closure of a random digraph, Random Structures Algorithms 1 (1990), 73­93. MR1068492 (91j:05093) 48. L. Kirousis, E. Kranakis, and D. Krizanc, Approximating the unsatisfiability threshold of random formulas, Proc. 4th European Symposium on Algorithms, 1996, pp. 27­38. 49. D. J. Kleitman, Families of non-disjoint subsets, J Combin Theory 1 (1966), 153­155. MR0193020 (33 #1242) 50. A. Kamath, R. Motwani, K. Palem, and P. Spirakis. Tail bounds for occupancy and the satisfiability threshold conjecture, Random Structures Algorithms 7 (1995), 59­89. MR1346284 (97b:68091) 51. S. Kirkpatrick and B. Selman, Critical behavior in the satisfiability of random Boolean expressions, Science 264 (1994), 1297­1301. MR1275579 (96e:68063) 52. T. Luczak, B. Pittel, and J. C. Wierman, The structure of a random graph at the point of the phase trasnsition, Trans Amer Math Soc 341 (1994), 721­748. MR1138950 (94d:05123) 53. T. Larrabee and Y. Tsuji, Evidence for satisfiability threshold for random 3CNF formulas, Proc. AAAI Symposium on Artificial Intelligence and NP-Hard Problems, 1993, p. 112. 54. T. Luczak, Component behavior near the critical point of the random graph process, Random Structures Algorithms 1 (1990), 287­310. MR1099794 (92c:05139) 55. C. McDiarmid, On the method of bounded differences, in Surveys in Combinatorics, 1989, pp. 148­188. MR1036755 (91e:05077) 56. M. M´ zard, G. Parisi, and M. A. Virasoro, Spin Glass Theory and Beyond, World Scientific, e Singapore, 1987. MR1026102 (91k:82066) 57. D. Mitchell, B. Selman, and H. Levesque, Hard and easy distributions of SAT problems, Proc 10th Natl Conf Artificial Intelligence, 1992, pp. 459­465. 58. R. Monasson and R. Zecchina, The entropy of the K-satisfiability problem, Phys Rev Lett 76 (1996), 3881. MR1388240 (97a:82053) 59. R. Monasson and R. Zecchina, Statistical mechanics of the random K-SAT model, Phys Rev E 56 (1997), 1357­1370. MR1464158 (98g:82022) 60. R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky, 2 + p-SAT: Relation of typical-case complexity to the nature of the phase transition, Random Structures Algorithms 15 (1999), 414­435. MR1716770 (2000i:68076) 61. B. Selman and S. Kirkpatrick, Critical behavior in the computational cost of satisfiability testing, Artificial Intelligence 81 (1996), 273­295. MR1396834 (98h:03018) 62. Y. Verhoeven, Random 2-SAT and unsatisfiability, Inf Process Lett 72 (1999), 119­123. MR1747696 (2000k:68074) 63. D. B. Wilson, (1998). 64. D. B. Wilson, The empirical values of the critical k-SAT exponents are wrong. Preprint math.PR/0005136 (2000). 65. E. M. Wright, The number of connected sparsely edged graphs, J Graph Theory 1 (1977), 317­330. MR0463026 (57 #2990) 66. E. M. Wright, The number of connected sparsely edged graphs III. Asymptotic results, J Graph Theory 4 (1980), 393­407. MR0595607 (82d:05070)

Note: This list reflects references listed in the original paper as accurately as possible with no attempt to correct errors.

c Copyright American Mathematical Society 2002, 2008


5 pages

Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate


You might also be interested in

Satisfiability Solvers