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.