Document Open Access Logo

Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT

Authors Tobias Friedrich, Anton Krohmer, Ralf Rothenberger, Thomas Sauerwald, Andrew M. Sutton

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.37.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Tobias Friedrich
Anton Krohmer
Ralf Rothenberger
Thomas Sauerwald
Andrew M. Sutton

Cite As Get BibTex

Tobias Friedrich, Anton Krohmer, Ralf Rothenberger, Thomas Sauerwald, and Andrew M. Sutton. Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.37

Abstract

Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. The worst-case hardness of SAT lies at the core of computational complexity theory. The average-case analysis of SAT has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures.

Despite a long line of research and substantial progress, nearly all theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This can be modeled by a scale-free distribution of the variables, which results in distributions closer to industrial SAT instances.

We study random k-SAT on n variables, m = Theta(n) clauses, and a power law distribution on the variable occurrences with exponent beta. We observe a satisfiability threshold at beta = (2k-1)/(k-1). This threshold is tight in the sense that instances with beta <= (2k-1)/(k-1)-epsilon for any constant epsilon > 0 are unsatisfiable with high probability (w.h.p.). For beta >= (2k-1)/(k-1)+epsilon, the picture is reminiscent of the uniform case: instances are satisfiable w.h.p. for sufficiently small constant clause-variable ratios m/n; they are unsatisfiable above a ratio m/n that depends on beta.

Subject Classification

Keywords
  • satisfiability
  • random structures
  • random SAT
  • power law distribution
  • scale-freeness
  • phase transitions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Dimitris Achlioptas, Amin Coja-Oghlan, and Federico Ricci-Tersenghi. On the solution-space geometry of random constraint satisfaction problems. Random Structures &Algorithms, 38(3):251-268, 2011. Google Scholar
  2. William Aiello, Fan Chung, and Linyuan Lu. A random graph model for power law graphs. Experimental Mathematics, 10(1):53-66, 2001. Google Scholar
  3. Dan Alistarh, Thomas Sauerwald, and Milan Vojnović. Lock-free algorithms under stochastic schedulers. In 34th Symp. Principles of Distributed Computing (PODC), pages 251-260, 2015. Google Scholar
  4. Carlos Ansótegui, Maria Luisa Bonet, Jesús Giráldez-Cru, and Jordi Levy. The fractal dimension of SAT formulas. In 7th Intl. Joint Conf. Automated Reasoning (IJCAR), pages 107-121, 2014. Google Scholar
  5. Carlos Ansótegui, Maria Luisa Bonet, Jesús Giráldez-Cru, and Jordi Levy. On the classification of industrial SAT families. In 18th Intl. Conf. of the Catalan Association for Artificial Intelligence (CCIA), pages 163-172, 2015. Google Scholar
  6. Carlos Ansótegui, Maria Luisa Bonet, and Jordi Levy. On the structure of industrial SAT instances. In 15th Intl. Conf. Principles and Practice of Constraint Programming (CP), pages 127-141, 2009. Google Scholar
  7. Carlos Ansótegui, Maria Luisa Bonet, and Jordi Levy. Towards industrial-like random SAT instances. In 21st Intl. Joint Conf. Artificial Intelligence (IJCAI), pages 387-392, 2009. Google Scholar
  8. Bengt Aspvall, Michael F Plass, and Robert Endre Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters, 8(3):121-123, 1979. Google Scholar
  9. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286:509-512, 1999. Google Scholar
  10. Yacine Boufkhad, Olivier Dubois, Yannet Interian, and Bart Selman. Regular random k-SAT: Properties of balanced formulas. J. Automated Reasoning, 35(1-3):181-200, 2005. Google Scholar
  11. Milan Bradonjic and Will Perkins. On sharp thresholds in random geometric graphs. In 18th Intl. Workshop on Randomization and Computation (RANDOM), pages 500-514, 2014. Google Scholar
  12. Karl Bringmann, Ralph Keusch, and Johannes Lengler. Geometric inhomogeneous random graphs. arXiv preprint arXiv:1511.00576, 2015. Google Scholar
  13. Václav Chvatal and Bruce Reed. Mick gets some (the odds are on his side). In 33rd Symp. Foundations of Computer Science (FOCS), pages 620-627, 1992. Google Scholar
  14. Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. Power-law distributions in empirical data. SIAM Review, 51(4):661-703, 2009. Google Scholar
  15. Amin Coja-Oghlan and Konstantinos Panagiotou. The asymptotic k-SAT threshold. Advances in Mathematics, 288:985-1068, 2016. Google Scholar
  16. Wenceslas Fernandez de la Vega. Random 2-SAT: results and problems. Theoretical Computer Science, 265(1-2):131-146, 2001. Google Scholar
  17. Josep Díaz, Lefteris M. Kirousis, Dieter Mitsche, and Xavier Pérez-Giménez. On the satisfiability threshold of formulas with three literals per clause. Theoretical Computer Science, 410(30-32):2920-2934, 2009. Google Scholar
  18. Jian Ding, Allan Sly, and Nike Sun. Proof of the satisfiability conjecture for large k. In 47th Symp. Theory of Computing (STOC), pages 59-68, 2015. Google Scholar
  19. D.P. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. Google Scholar
  20. Ehud Friedgut. Sharp thresholds of graph properties, and the k-SAT problem. J. ACM, 12(4):1017-1054, 1999. Google Scholar
  21. Tobias Friedrich, Anton Krohmer, Ralf Rothenberger, Thomas Sauerwald, and Andrew M. Sutton. Bounds on the satisfiability threshold for power law distributed random SAT. arXiv preprint arXiv:1706.08431, 2017. Google Scholar
  22. Andreas Goerdt. A threshold for unsatisfiability. J. Computer & System Sciences, 53(3):469-486, 1996. Google Scholar
  23. Mohammad Taghi Hajiaghayi and Gregory B. Sorkin. The satisfiability threshold of random 3-SAT is at least 3.52. Technical Report RC22942, IBM, October 2003. Google Scholar
  24. Alexis C. Kaporis, Lefteris M. Kirousis, and Efthimios G. Lalas. The probabilistic analysis of a greedy satisfiability algorithm. Random Structures &Algorithms, 28(4):444-480, 2006. Google Scholar
  25. Lefteris M Kirousis, Evangelos Kranakis, Danny Krizanc, and Yannis C Stamatiou. Approximating the unsatisfiability threshold of random formulas. Random Structures &Algorithms, 12(3):253-269, 1998. Google Scholar
  26. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Phys. Rev. E, 82:036106, Sep 2010. Google Scholar
  27. Colin McDiarmid. On a correlation inequality of Farr. Combinatorics, Probability & Computing, 1(02):157-160, 1992. Google Scholar
  28. Marc Mézard, Giorgio Parisi, and Riccardo Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297(5582):812-815, 2002. Google Scholar
  29. M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45(2):pp. 167-256, 2003. Google Scholar
  30. Mark EJ Newman. Power laws, pareto distributions and Zipf’s law. Contemporary physics, 46(5):323-351, 2005. Google Scholar
  31. Bo Söderberg. General formalism for inhomogeneous random graphs. Phys. Rev. E, 66(6):066121, 2002. Google Scholar
  32. Remco van der Hofstad. Random graphs and complex networks. Available at https://www.win.tue.nl/~rhofstad/NotesRGCN.pdf, 2011.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact