ProV Logo
0
An alternate view of complexity in k-SAT...
Krishnamurthy, Supri...

Free

An alternate view of complexity in k-SAT problems by Krishnamurthy, Supriya ( Author )
Lemonjar Open Access
N.A
08-12-2014
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 non-rigorous 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 1-RSB assumption. Our method hence provides alternate interpretations as well as motivations for the key equations in the RSB approach.
-
Article
pdf
36.88 KB
English
-
MYR 0.01
-
https://arxiv.org/abs/1412.2460
Share this eBook