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.