  To study the structure of solutions for random k-SAT and random CSPs, this
paper introduces the concept of average similarity degree to characterize how
solutions are similar to each other. It is proved that under certain
conditions, as r (i.e. the ratio of constraints to variables) increases, the
limit of average similarity degree when the number of variables approaches
infinity exhibits phase transitions at a threshold point, shifting from a
smaller value to a larger value abruptly. For random k-SAT this phenomenon will
occur when k>4 . It is further shown that this threshold point is also a
singular point with respect to r in the asymptotic estimate of the second
moment of the number of solutions. Finally, we discuss how this work is helpful
to understand the hardness of solving random instances and a possible
application of it to the design of search algorithms.
