Recent work on heuristics and the satisfiability threshold of random constraint satisfaction problems has centered around the structure and connectivity of the solution space. I will review this area, and present new dichotomy theorems that are motivated by it. In particular, we study onnectivity properties of the space of solutions of Boolean CSPs and establish both computational and structural dichotomies in Schaefer's framework.
We establish dichotomy theorems for the complexity of the connectivity and st-connectivity questions for the graph of solutions of Boolean formulas, as well as for the diameter of the connected components of the solution space. Our results assert that the intractable side of the computational dichotomies is PSPACE-complete, while the tractable side - which includes but is not limited to all problems with polynomial time algorithms for satisfiability - is in P for the st-connectivity question, and in coNP for the connectivity question. The diameter of components can be exponential for the PSPACE-complete cases, whereas in all other cases it is linear. Thus, small diameter and tractability of the connectivity problems are remarkably aligned.
The crux of our results is an expressibility theorem showing that a large class of Boolean CSPs can be reduced to each other in a way that preserves the structural properties of the solution space.