Previous research has shown that 3-SAT problems are easy to solve both when the “constrainedness” (the ratio of the number of clauses to the number of variables) is low and when it is high, abruptly transitioning from easy to hard in a very narrow region of constrainedness. Most of these “phase transition” studies were done on SAT instances that follow uniform random distribution. In such a distribution, variables take part in clauses with uniform probability, and clauses are independent (uncorrelated). The assumptions of uniform random distribution are, however, not satisfied when we consider SAT instances that result from real problems. Our project aims for a deeper understanding of the hardness of SAT problems that arise in practice. In particular, we study two key questions: (1) How does the phase transition behavior change with more realistic and natural distributions of SAT problems? and (2) Can we gain an understanding of the phase transition in terms of the network structure of these SAT problems? Our hypothesis is that the network properties help predict and explain how the easy-to-hard problem transition for realistic SAT problems differs from those for uniform random distribution.

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).