On the Average Similarity Degree between Solutions of Random k-SAT and Random CSPs
<|reference_start|>On the Average Similarity Degree between Solutions of Random k-SAT and Random CSPs: 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.<|reference_end|>
@article{xu2000on,
    title={On the Average Similarity Degree between Solutions of Random k-SAT and
  Random CSPs},
    author={Ke Xu and Wei Li},
    journal={Discrete Applied Mathematics, 136(2004):125-149.},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0008008},
    primaryClass={cs.AI cs.CC cs.DM}
}