A Computational Trichotomy for Connectivity of Boolean Satisfiability

Abstract

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 heuristics and the satisfiability threshold, in 2006, Gopalan et al. studied connectivity properties of the solution graph and related complexity issues for constraint satisfaction problems [11]. They found dichotomies for the diameter of connected components and for the complexity of the st-connectivity question, and conjectured a trichotomy for the connectivity question. Their results could be improved based on findings by Makino et al. [15].

Building on this work, we here prove the trichotomy for the connectivity question. Also, we correct a minor mistake in [11], which leads to a slight shift of the boundaries towards the hard side.