15 citations · 17 across the 2 of their papers we have counts for
Showing 2000 · cs.AIShow all
3 papers · 2 filters
cs.AI2000
On the Average Similarity Degree between Solutions of Random k-SAT and Random CSPs
Ke Xu, Wei Li
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 ea…
cs.AI2000
The SAT Phase Transition
Ke Xu, Wei Li
Phase transition is an important feature of SAT problem. For random k-SAT model, it is proved that as r (ratio of clauses to variables) increases, the structure of solutions will u…
cs.AI2000
Exact Phase Transitions in Random Constraint Satisfaction Problems
Ke Xu, Wei Li
In this paper we propose a new type of random CSP model, called Model RB, which is a revision to the standard Model B. It is proved that phase transitions from a region where almos…