Phase Transition and Network Structure in Realistic SAT Problems
  A fundamental question in Computer Science is understanding when a specific
class of problems go from being computationally easy to hard. Because of its
generality and applications, the problem of Boolean Satisfiability (aka SAT) is
often used as a vehicle for investigating this question. A signal result from
these studies is that the hardness of SAT problems exhibits a dramatic
easy-to-hard phase transition with respect to the problem constrainedness. Past
studies have however focused mostly on SAT instances generated using uniform
random distributions, where all constraints are independently generated, and
the problem variables are all considered of equal importance. These assumptions
are unfortunately not satisfied by most real problems. Our project aims for a
deeper understanding of hardness of SAT problems that arise in practice. We
study two key questions: (i) How does easy-to-hard transition change with more
realistic distributions that capture neighborhood sensitivity and
rich-get-richer aspects of real problems and (ii) Can these changes be
explained in terms of the network properties (such as node centrality and
small-worldness) of the clausal networks of the SAT problems. Our results,
based on extensive empirical studies and network analyses, provide important
structural and computational insights into realistic SAT problems. Our
extensive empirical studies show that SAT instances from realistic
distributions do exhibit phase transition, but the transition occurs sooner (at
lower values of constrainedness) than the instances from uniform random
distribution. We show that this behavior can be explained in terms of their
clausal network properties such as eigenvector centrality and small-worldness
(measured indirectly in terms of the clustering coefficients and average node
distance).
