An alternate view of complexity in k-SAT problems

Abstract

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.

5 pages, 3 figures, typos corrected

References in corpus (7)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Reconstruction on trees and spin glass transition
• On the freezing of variables in random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Grand canonical and canonical solution of self-avoiding walks with up to three monomers per site on the Bethe lattice
• Adversarial Satisfiability Problem
• On the behaviour of random K-SAT on trees