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

Simple item page
dc.creatorXu, Ke
dc.creatorLi, Wei
dc.date2000-08-11
dc.date2002-04-07
dc.date.accessioned2026-07-07T03:16:26Z
dc.date.available2026-07-07T03:16:26Z
dc.descriptionTo 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.
dc.description22 pages, the final version to appear in Discrete Applied Mathematics
dc.identifierhttps://arxiv.org/abs/cs/0008008
dc.identifierhttp://arxiv.org/abs/cs/0008008
dc.identifierDiscrete Applied Mathematics, 136(2004):125-149.
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30356
dc.subjectArtificial Intelligence
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.subjectF.2.2; I.2.8
dc.titleOn the Average Similarity Degree between Solutions of Random k-SAT and Random CSPs
dc.typetext

Files

Collections

arXiv