Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Satisfiability Threshold for Power Law Random 2-SAT in Configuration Model

  • Conference paper
  • First Online:
Theory and Applications of Satisfiability Testing – SAT 2019 (SAT 2019)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 11628))

Abstract

The Random Satisfiability problem has been intensively studied for decades. For a number of reasons the focus of this study has mostly been on the model, in which instances are sampled uniformly at random from a set of formulas satisfying some clear conditions, such as fixed density or the probability of a clause to occur. However, some non-uniform distributions are also of considerable interest. In this paper we consider Random 2-SAT problems, in which instances are sampled from a wide range of non-uniform distributions.

The model of random SAT we choose is the so-called configuration model, given by a distribution \(\xi \) for the degree (or the number of occurrences) of each variable. Then to generate a formula the degree of each variable is sampled from \(\xi \), generating several clones of the variable. Then 2-clauses are created by choosing a random paritioning into 2-element sets on the set of clones and assigning the polarity of literals at random.

Here we consider the random 2-SAT problem in the configuration model for power-law-like distributions \(\xi \). More precisely, we assume that \(\xi \) is such that its right tail \(F_{\xi }(x)\) satisfies the conditions \(W\ell ^{-\alpha }\le F_{\xi }(\ell )\le V\ell ^{-\alpha }\) for some constants V, W. The main goal is to study the satisfiability threshold phenomenon depending on the parameters \(\alpha ,V,W\). We show that a satisfiability threshold exists and is determined by a simple relation between the first and second moments of \(\xi \).

This work was supported by an NSERC Discovery grant.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Achlioptas, D.: Lower bounds for random 3-SAT via differential equations. Theor. Comput. Sci. 265(1–2), 159–185 (2001)

    Article  MathSciNet  Google Scholar 

  2. Achlioptas, D., Moore, C.: Random \(k\)-SAT: two moments suffice to cross a sharp threshold. SIAM J. Comput. 36(3), 740–762 (2006)

    Article  MathSciNet  Google Scholar 

  3. Aiello, W., Graham, F.C., Lu, L.: A random graph model for power law graphs. Exp. Math. 10(1), 53–66 (2001)

    Article  MathSciNet  Google Scholar 

  4. Ansótegui, C., Bonet, M.L., GirÁldez-Cru, J., Levy, J.: Community structure in industrial SAT instances (2016)

    Google Scholar 

  5. Ansótegui, C., Bonet, M.L., Levy, J.: On the structure of industrial SAT instances. In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 127–141. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04244-7_13

    Chapter  Google Scholar 

  6. Ansótegui, C., Bonet, M.L., Levy, J.: Towards industrial-like random SAT instances. In: IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, 11–17 July 2009, pp. 387–392 (2009)

    Google Scholar 

  7. Ansótegui, C., Bonet, M.L., Levy, J.: Scale-free random SAT instances (2017). https://arxiv.org/abs/1708.06805v2

  8. Ansótegui, C., Bonet, M.L., Levy, J., Manyà, F.: Measuring the hardness of SAT instances. In: Proceedings of the 23rd National Conference on Artificial Intelligence, AAAI 2008, vol. 1, pp. 222–228 (2008)

    Google Scholar 

  9. Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inf. Process. Lett. 8(3), 121–123 (1979)

    Article  MathSciNet  Google Scholar 

  10. Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)

    Article  MathSciNet  Google Scholar 

  11. Bollobás, B., Riordan, O.: Mathematical results on scale-free random graphs. In: Handbook of Graphs and Networks, pp. 1–34. Wiley-VCH (2002)

    Google Scholar 

  12. Bollobás, B., Riordan, O., Spencer, J., Tusnády, G.E.: The degree sequence of a scale-free random graph process. Random Struct. Algorithms 18(3), 279–290 (2001)

    Article  MathSciNet  Google Scholar 

  13. Boufkhad, Y., Dubois, O., Interian, Y., Selman, B.: Regular random k-SAT: properties of balanced formulas. J. Autom. Reason. 35(1–3), 181–200 (2005)

    MathSciNet  MATH  Google Scholar 

  14. Braunstein, A., Mézard, M., Zecchina, R.: Survey propagation: an algorithm for satisfiability. Random Struct. Algorithms 27(2), 201–226 (2005)

    Article  MathSciNet  Google Scholar 

  15. Chvátal, V., Reed, B.A.: Mick gets some (the odds are on his side). In: 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24–27 October 1992, pp. 620–627 (1992)

    Google Scholar 

  16. Clauset, A., Shalizi, C., Newman, M.: Power-law distributions in empirical data. SIAM Rev. 51(4), 661–703 (2009)

    Article  MathSciNet  Google Scholar 

  17. Coja-Oghlan, A.: A better algorithm for random \(k\)-SAT. SIAM J. Comput. 39(7), 2823–2864 (2010)

    Article  MathSciNet  Google Scholar 

  18. Coja-Oghlan, A., Panagiotou, K.: Going after the k-SAT threshold. In: Symposium on Theory of Computing Conference, STOC 2013, Palo Alto, CA, USA, 1–4 June 2013, pp. 705–714 (2013)

    Google Scholar 

  19. Cook, S.A., Mitchell, D.G.: Finding hard instances of the satisfiability problem: a survey. In: Proceedings of a DIMACS Workshop on Satisfiability Problem: Theory and Applications, Piscataway, New Jersey, USA, 11–13 March 1996, pp. 1–18 (1996)

    Google Scholar 

  20. Cooper, C., Frieze, A., Sorkin, G.B.: Random 2-SAT with prescribed literal degrees. Algorithmica 48(3), 249–265 (2007)

    Article  MathSciNet  Google Scholar 

  21. Díaz, J., Kirousis, L.M., Mitsche, D., Pérez-Giménez, X.: On the satisfiability threshold of formulas with three literals per clause. Theor. Comput. Sci. 410(30–32), 2920–2934 (2009)

    Article  MathSciNet  Google Scholar 

  22. Ding, J., Sly, A., Sun, N.: Proof of the satisfiability conjecture for large \(k\). In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, 14–17 June 2015, pp. 59–68 (2015)

    Google Scholar 

  23. Dubios, O., Boufkhad, Y.: A general upper bound for the satisfiability threshold of random r-SAT formulae. J. Algorithms 24(2), 395–420 (1997)

    Article  MathSciNet  Google Scholar 

  24. Dubois, O., Boufkhad, Y., Mandler, J.: Typical random 3-SAT formulae and the satisfiability threshold. Electron. Colloq. Comput. Complex. (ECCC) 10(007) (2003)

    Google Scholar 

  25. Franco, J., Paull, M.C.: Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem. Discrete Appl. Math. 5(1), 77–87 (1983)

    Article  MathSciNet  Google Scholar 

  26. Friedgut, E.: Sharp thresholds of graph properties, and the \(k\)-SAT problem. J. ACM 12(4), 1017–1054 (1999)

    MathSciNet  MATH  Google Scholar 

  27. Friedrich, T., Krohmer, A., Rothenberger, R., Sauerwald, T., Sutton, A.M.: Bounds on the satisfiability threshold for power law distributed random SAT. In: 25th Annual European Symposium on Algorithms, ESA 2017, Vienna, Austria, 4–6 September 2017, pp. 37:1–37:15 (2017)

    Google Scholar 

  28. Friedrich, T., Rothenberger, R.: Sharpness of the satisfiability threshold for non-uniform random k-SAT. In: Beyersdorff, O., Wintersteiger, C.M. (eds.) SAT 2018. LNCS, vol. 10929, pp. 273–291. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94144-8_17

    Chapter  MATH  Google Scholar 

  29. Giráldez-Cru, J., Levy, J.: Generating SAT instances with community structure. Artif. Intell. 238(C), 119–134 (2016)

    Article  MathSciNet  Google Scholar 

  30. Goerdt, A.: A threshold for unsatisfiability. J. Comput. Syst. Sci. 53(3), 469–486 (1996)

    Article  MathSciNet  Google Scholar 

  31. Kaporis, A.C., Kirousis, L.M., Lalas, E.G.: The probabilistic analysis of a greedy satisfiability algorithm. Random Struct. Algorithms 28(4), 444–480 (2006)

    Article  MathSciNet  Google Scholar 

  32. Kim, J.H.: The Poisson cloning model for random graphs, random directed graphs and random k-SAT problems. In: Chwa, K.-Y., Munro, J.I.J. (eds.) COCOON 2004. LNCS, vol. 3106, p. 2. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27798-9_2

    Chapter  MATH  Google Scholar 

  33. Kirousis, L.M., Kranakis, E., Krizanc, D., Stamatiou, Y.C.: Approximating the unsatisfiability threshold of random formulas. Random Struct. Algorithms 12(3), 253–269 (1998)

    Article  MathSciNet  Google Scholar 

  34. Krioukov, D.V., Papadopoulos, F., Kitsak, M., Vahdat, A., Boguñá, M.: Hyperbolic geometry of complex networks. CoRR abs/1006.5169 (2010)

    Google Scholar 

  35. Krzakała, F., Montanari, A., Ricci-Tersenghi, F., Semerjian, G., Zdeborová, L.: Gibbs states and the set of solutions of random constraint satisfaction problems. PNAS 104(25), 10318–10323 (2007)

    Article  MathSciNet  Google Scholar 

  36. Mézard, M., Parisi, G., Zecchina, R.: Analytic and algorithmic solution of random satisfiability problems. Science 297(5582), 812–815 (2002)

    Article  Google Scholar 

  37. Newman, M.: Power laws, Pareto distributions and Zipf’s law. Contemp. Phys. 46(5), 323–351 (2005)

    Article  Google Scholar 

  38. Omelchenko, O., Bulatov, A.: Concentration inequalities for sums of random variables, each having power bounded tails (2018). https://arxiv.org/abs/1903.02529

  39. Selman, B., Mitchell, D.G., Levesque, H.J.: Generating hard satisfiability problems. Artif. Intell. 81(1–2), 17–29 (1996)

    Article  MathSciNet  Google Scholar 

  40. de la Vega, W.F.: Random 2-SAT: results and problems. Theor. Comput. Sci. 265(1–2), 131–146 (2001)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Simon Fraser University, Burnaby, Canada

    Oleksii Omelchenko & Andrei A. Bulatov

Authors
  1. Oleksii Omelchenko
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrei A. Bulatov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andrei A. Bulatov .

Editor information

Editors and Affiliations

  1. University of Lisbon, Lisbon, Portugal

    Mikoláš Janota

  2. University of Lisbon, Lisbon, Portugal

    Inês Lynce

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Omelchenko, O., Bulatov, A.A. (2019). Satisfiability Threshold for Power Law Random 2-SAT in Configuration Model. In: Janota, M., Lynce, I. (eds) Theory and Applications of Satisfiability Testing – SAT 2019. SAT 2019. Lecture Notes in Computer Science(), vol 11628. Springer, Cham. https://doi.org/10.1007/978-3-030-24258-9_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-24258-9_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-24257-2

  • Online ISBN: 978-3-030-24258-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation