Consistency and Random Constraint Satisfaction Models
  In this paper, we study the possibility of designing non-trivial random CSP
models by exploiting the intrinsic connection between structures and
typical-case hardness. We show that constraint consistency, a notion that has
been developed to improve the efficiency of CSP algorithms, is in fact the key
to the design of random CSP models that have interesting phase transition
behavior and guaranteed exponential resolution complexity without putting much
restriction on the parameter of constraint tightness or the domain size of the
problem. We propose a very flexible framework for constructing problem
instances withinteresting behavior and develop a variety of concrete methods to
construct specific random CSP models that enforce different levels of
constraint consistency. A series of experimental studies with interesting
observations are carried out to illustrate the effectiveness of introducing
structural elements in random instances, to verify the robustness of our
proposal, and to investigate features of some specific models based on our
framework that are highly related to the behavior of backtracking search
algorithms.
