A Computational Trichotomy for Connectivity of Boolean Satisfiability
Konrad W. Schwerdtfeger · Journal on Satisfiability Boolean Modeling and Computation · 2014
For Boolean satisfiability problems, the structure of the solution space is characterized by the solution graph, where the vertices are the solutions, and two solutions are connected iff they differ in exactly one variable. Motivated by research on h