Change search
ReferencesLink to record
Permanent link

Direct link
Exact satisfiability threshold for k-satisfiability problems on a Bethe lattice
Stockholm University, Faculty of Science, Department of Physics.
Number of Authors: 2
2015 (English)In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 92, no 4, 042144Article in journal (Refereed) Published
Abstract [en]

The satisfiability threshold for constraint satisfaction problems is that value of the ratio of constraints (or clauses) to variables, above which the probability that a random instance of the problem has a solution is zero in the large system limit. Two different approaches to obtaining this threshold have been discussed in the literature: using first or second moment methods which give rigorous bounds or using the nonrigorous but powerful replica-symmetry-breaking (RSB) approach, which gives very accurate predictions on random graphs. In this paper, we lay out a different route to obtaining this threshold on a Bethe lattice. We need make no assumptions about the solution-space structure, a key assumption in the RSB approach. Despite this, our expressions and threshold values exactly match the best predictions of the cavity method under the one-step RSB hypothesis. In addition we can use the same procedure to obtain other useful quantities on the Bethe lattice such as the second moment of the number of solutions. Our method hence provides alternate interpretations as well as motivations for the key equations in the RSB approach.

Place, publisher, year, edition, pages
2015. Vol. 92, no 4, 042144
National Category
Physical Sciences Mathematics
Identifiers
URN: urn:nbn:se:su:diva-123523DOI: 10.1103/PhysRevE.92.042144ISI: 000363242100001OAI: oai:DiVA.org:su-123523DiVA: diva2:874970
Available from: 2015-11-30 Created: 2015-11-27 Last updated: 2015-11-30Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Krishnamurthy, Supriya
By organisation
Department of Physics
In the same journal
Physical Review E. Statistical, Nonlinear, and Soft Matter Physics
Physical SciencesMathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 8 hits
ReferencesLink to record
Permanent link

Direct link