On the Average Similarity Degree between Solutions of Random k-SAT and Random CSPs

Details On the Average Similarity Degree between Solutions of Random k-SAT and Random CSPs On the Average Similarity Degree between Solutions of Random k-SAT and Random CSPs

2000-08-11

arxiv.org/abs/cs/0008008v2

Discrete Applied Mathematics, 136(2004):125-149.

Computer Science

Artificial Intelligence

22 pages, the final version to appear in Discrete Applied Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the Average Similarity Degree between Solutions of Random k-SAT and Random CSPs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Average Similarity Degree between Solutions of Random k-SAT and Random CSPs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Average Similarity Degree between Solutions of Random k-SAT and Random CSPs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-724024