Ideas from physics have predicted a number of important properties of
sparse random constraint satisfaction problems such as the satisfiability
threshold and the free energy (the exponential growth rate of the number of
solutions). Another prediction is the condensation regime where most of the
solutions are contained in a small number of clusters and the overlap of
two random solutions is concentrated on two points. We establish this
phenomenon for the first time in the random regular NAESAT model.