Constructing an Asymptotic Phase Transition in Random Binary
Constraint Satisfaction Problems
Research Report 2000.02, School of Computer Studies, University of Leeds,
January 2000.
Barbara M Smith
Abstract
The standard models used to generate random binary constraint satisfaction
problems are described. At the problem sizes studied experimentally, a
phase transition is seen as the constraint tightness is varied. However,
Achlioptas et al. showed that if the problem size (number of variables)
increases while the remaining parameters are kept constant, asymptotically
almost all
instances are unsatisfiable. In this paper, an alternative scheme for one
of the standard models is
proposed in which both the number of values in each variables's domain
and the average degree of the constraint graph are increased with problem
size. It is shown that with this scheme there is asymptotically a range of
values
of the constraint tightness in which instances are trivially satisfiable
with probability at least 0.5 and a range in which instances are almost all
unsatisfiable; hence there is a crossover point at some value of the
constraint tightness between these two ranges. This scheme is compared to
a similar scheme due to Xu and Li.
Back to "Barbara Smith
- Publications on Constraint Programming"