There is more to say about what's going on
as we increase the density.
As you might imagine,
the hardness of the problem has to do
with the structure of the landscape.
So remember how many optimization problems
are hard once their landscapes,
instead of having a single big peak
have lots of local optima.
Well, what happens in random set is
very similar.
Imagine taking a topographic map
of a mountain range
and kind of slicing it off at a particular
altitude
perhaps the altitude, where indeed, all
of the clauses are satisfied.
If you have that Mount Fuji landscape, and
you slice it off,
then you get a nice big plateau of
solutions.
And any solution in this rough area does
pretty well
and moreover, the set of solutions is
connected to each other.
You could walk from any to any other by
changing one variable at a time.
And there would be a way to do that
while
continuing to satisfy the entire formula.
Well, guess what?
As we increase the density,
there is something called Clustering
Transition.
There are still many solutions
but now, just as you get many
mountain peaks in a hard problem,
you now have little clusters of solutions,
exponentially many clusters of solutions
and not only are these separated from
each other,
but in order to get from one to the other,
you would have to go down through a
valley
where you unsatisfy, dissatisfy, a large
number of clauses
in order to travel from this cluster
to that cluster.
Physicists would say that this system
has become glassy.
And that you would have to cross over a
difficult energy barrier
to get from one cluster to another.
At that point, an algorithm which is
trying to sample fairly,
from all possible solutions,
would have real trouble
because, for instance, it was the kind
of
Monte Carlo algorithm, which is popular
in many sciences, which runs
around the space of possible
solutions by flipping individual variables
Well it would be stuck in whatever cluster
it started out in.
It would be very unwilling to pass through
this zone of really bad nonsolutions
in order to get to another cluster
over there.
As we increase the density further,
more structural transitions happen.
Again, these formulas are still
satisfiable,
but more things are happening to the set,
the structure, of solutions.
Above the clustering transition is another
transition
called the Condensation Transition.
At this point, a few of the clusters
dominate the set of possible solutions.
And if you're not lucky enough to start
out in one of them,
then in some sense you're not dealing
with a typical solution.
Beyond that is yet another transition,
called the Freezing,
or Rigidity Transition.
Now, things are starting to get
very brittle,
very tight.
Now, in almost all clusters,
most of the variables have to be set in
a specific way.
If they're not set in that way, there are
contradictions.
If you think about it, it is intuitive
that now a search algorithm
is in real trouble.
Let's say you start out kind of looking
down on this
vast space of possible solutions, if you
have no idea which way to go
you start setting variables and zooming
in on part of the solution space
hoping to find a viable cluster of
solutions there.
But, these clusters are frozen so that,
for instance, half their variables
have to be set precisely.
To particular values, or all solutions in
that vicinity will be disqualified.
Well, as you travel down your search tree
zooming in on parts of the space
you're setting more and more variables.
If you get even a single variable wrong,
setting it to the value that is opposite
to the one that's frozen into
that cluster then you're going to miss
that cluster completely.
You've gone down a branch of the
search tree below which there are no
solutions at all.
But you don't know that yet,
you're going to have to explore
that sub-tree and that will take you
exponential time.
So our current belief is that this
Freezing Transition
is when this problem really gets hard.
That it really takes exponential time for
the types of algorithms that
anyone has been able to think of so far
to find even a single solution to the
random set problem.
So what's the lesson of all this?
It's not just this one transition at
the top
that takes us from satisfiable to
unsatisfiable,
there is a whole host of structural
changes that the landscape undergoes
some of which make it hard to sample
fairly
from the space of possible solutions
and some of it, some of which
we believe, make it hard even to
find a single solution
or tell if there is one.