One line of research into Boolean satisfiability is the development of “dichotomy theorems” following those of [{\it T. J. Schaefer}, “The complexity of satisfiability problems”, in: Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), 216‒226 (1978)]; Schaefer’s theorem divided Boolean satisfiability problems into PTIME and NP-complete problems. This paper presents dichotomy theorems concerning properties of the solution spaces of Boolean formulas, particularly connectivity and $s,t$-connectivity. The framework starts with $k$-conjunctive normal forms of Boolean formulas, each conjunct being a combination $φ_i(P_1, \dots, P_k)$. Given a set ${\cal S}$ of “logical relations” $R_i \subseteq \{0,1\}^k$, one can ask the following question of a given $k$-CNF $φ= φ_1\land \cdots \land φ_n$: Does there exist a truth assignment $ξ_{i,j} \mapsto \{ 0, 1 \}$, $i = 1, \ldots, n$, $j = 1, \ldots, k$, such that (1) for each $i, j$, $P_{i, j}$ is of truth value $ξ_{i,j}$ and (2) for each $i$, there exists $R_i \in{\cal S}$ such that $R_i(ξ_{i,1}, \dots, ξ_{i,k})$, and (3) this induces an assignment of truth values to atoms and (4) assuming this assignment of truth values, the CNF formula $φ$ is satisfied? If ${\cal S}$ is a set of logical relations (all of “rank” $k$), this question then becomes the SAT(${\cal S}$) query; many satisfiability problems (including the 3-CNF satisfiability problem) are equivalent to SAT(${\cal S}$) queries for various sets ${\cal S}$. (The set of all formulas so expressible from ${\cal S}$ ‒ perhaps with some permutations of literals within conjuncts (careful!) ‒ are the CNF(${\cal S}$) formulas.) Schaefer presented several syntactic criteria such that if all the relations in ${\cal S}$ satisfied one of these criteria, then SAT(${\cal S}$) was PTIME-computable; otherwise, SAT(${\cal S}$) was NP-complete. This paper extends Schaefer’s result by exploring the solution spaces of CNF$({\cal S}$) formulas. The critical notion is that of {\it tightness}, which entails a set of syntactic criteria properly extending Schaefer’s. There are two classes of results, largely regarding the solution space $G(φ)$ of truth assignments (within the hypercube in which Boolean tuples are embedded) satisfying the CNF$({\cal S}$) formula $φ$. Let CONN(${\cal S}$) be the query “given $φ$ in CNF(${\cal S}$), is $G(φ)$ connected?” { indent=4mm \item{$\bullet$} If $\mathcal S$ is not tight, then the diameter of $G(φ)$ is exponential in the number of variables of $φ$, and CONN$({\cal S}$) is PSPACE-complete. \item{$\bullet$} If $\mathcal S$ is tight, the diameter of $G(φ$) is linear in the number of variables of $φ$, and CONN$({\cal S}$) is co-NP-computable. } Path connectivity between two truth assignments of $G(φ)$ is also investigated, and, in fact, a number of related and interesting issues are explored.
Reviewer: Gregory Loren McColm (Tampa)