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 (satisfiability) 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. A key assumption in the
RSB approach is that the ground state structure of this class of problems exhibits clustering, and a key quantity
is hence the logarithm of the number of solution clusters. This quantity is called the 'complexity'.
In this talk, we will lay out a different route to obtaining
the satisfiability threshold on a Bethe lattice. We need
make no assumptions about the solution-space structure, but despite this,
our expressions and threshold values
exactly match the best predictions of the RSB approach for all
variants of the k-SAT problem.
Our method hence provides alternate interpretations as well as
motivations for the key equations in the RSB approach.
