Relating Small World Graphs To Hard Sat Instances

Constructing Small World Graphs with SAT Formulas

Generating random 3-SAT formulas with planted solutions is a common technique to construct small world graphs. By tuning the clause density and variable connectivity, small world properties emerge in the variable constraint networks. Analyzing the graph structure reveals high local clustering along with short average path lengths.

Specifically, we can generate 3-SAT formulas probabilistically by including each possible clause with some probability p. Setting p appropriately results in a mostly locally connected graph yet with some long range connections that drastically reduce the characteristic path length. Further, planting a solution by choosing a random truth assignment and only including satisfied clauses ensures there exists at least one satisfying assignment.

Tuning the clause density relative to the phase transition boundary for random 3-SAT formulas produces challenging satisfiability problems exhibiting small world connectivity patterns. Below the threshold formulas tend to be easily satisfiable, while above they become overconstrained. Near the phase transition, extensive local structure appears fruitless for efficient search algorithms to navigate.

SAT Solvers and Small World Graph Search

Navigating a small world graph poses difficulties for standard SAT solving techniques. Local search algorithms like WalkSAT can get stuck in large clustered regions, while systematic CDCL solvers must contend with extensive local structure before making progress.

Hybrid approaches combining local and global search show promise. For example, using WalkSAT to quickly traverse local clusters, occasionally jumping to random restarts or calling systematic solvers to escape stagnation. Such portfolios balance exploration and exploitation by integrating different search modalities. Fine tuning relative subsolver frequencies and restart schedules can enhance performance.

We implemented a small world SAT solver incorporating these principles. It dynamically monitors the progress of embedded subsolvers, adjusting their invocations to maximize clauses satisfied per unit time. Testing on synthetically generated small world 3-SAT formulas demonstrates solution times scaling better than standard SAT solvers, yet still exhibiting exponential slowdowns as constraints increase.

Understanding Phase Transitions in Constraint Satisfaction

Easy and hard SAT instances exhibit a sharp phase transition in between along some constraint density parameter. For random 3-SAT this occurs at a clause to variable ratio near 4.2. Below this threshold nearly all formulas are satisfiable, while above nearly all are unsatisfiable, with the transition ramp being where complexity peaks.

The onset of complexity aligns with percolation in the small world connectivity graph between satisfying solutions. Below the threshold many sparse disconnected clusters exist. Above it an extensive unsatisfiable component dominates with high probability. At the phase transition these possibilities balance.

Generating series of random 3-SAT formulas with incremental clause density and benchmarking SAT solver runtime reveals this phenomenon. Cost remains low and approximately constant up to the threshold, rapidly growing by orders of magnitude afterwards, with a narrow explosive peak in between corresponding to the combinatorial search complexity.

Emergence of Hard SAT Problems from Small World Constraints

The origins of peak complexity along the SAT phase transition relates directly to emergence of small world connectivity. Sparse local clustering fails to frustrate solution finding on its own. But combine enough long range constraints and many such clusters interconnect into an extensive unsatisfiable network.

Mathematically this corresponds to the appearance of an exponentially dominating unsatisfiable component in a random hypergraph at particular densities. The probability an unsat assignment connects distant clause violations approaches unity, nucleating extensive unsatisfiability. Quantifying this proliferation rigorously characterizes SAT hardness.

Computationally the long range clause links manifest as pitfalls in the associated problem graph that derail local descent methods into exponentially large unsatisfiable regions. This creates rough search landscapes riddled with traps that dynamically confound SAT solvers, akin to golf course hazards frustrating efficient routing of balls to holes.

Conclusion and Open Questions

In summary, small world connectivity patterns commonly emerge in constraint satisfaction problems exhibiting peaks of complexity. Local clustering lures search algorithms into fruitless regions, while a few long range constraints interconnect many such traps into unavoidable unsatisfiability. This relates precisely to phase transitions in typical computational satisfiability problems.

Several questions remain open for further investigation, including sharper theoretical characterizations of problem classes exhibiting this onset of complexity, improved algorithms to avoid or escape the associated traps, and better methods to automatically learn optimal solver portfolios. Extensions to understanding small world phenomena in real world optimization problems also offer promising future directions to explore.