Name
Abstract | ||
|---|---|---|
Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics, and threshold phenomena. Recent work on heuristics and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions of Boolean satisfiability problems and establish various dichotomies in Schaefer's framework. On the structural side, we obtain dichotomies for the kinds of subgraphs of the hypercube that can be induced by the solutions of Boolean formulas, as well as for the diameter of the connected components of the solution space. On the computational side, we establish dichotomy theorems for the complexity of the connectivity and $st$-connectivity questions for the graph of solutions of Boolean formulas. 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, diameter and complexity of the connectivity problems are remarkably aligned. The crux of our results is an expressibility theorem showing that in the tractable cases, the subgraphs induced by the solution space possess certain good structural properties, whereas in the intractable cases, the subgraphs can be arbitrary. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/07070440X | international colloquium on automata, languages and programming |
Keywords | DocType | Volume |
boolean satisfiability,boolean formula,connectivity question,satisfiability threshold,structural side,boolean satisfiability problem,solution space,structural dichotomies,intractable side,tractable side,connectivity problem,computational side,graph connectivity,connected component,computational complexity,satisfiability | Journal | 38 |
Issue | ISSN | ISBN |
6 | Extended abstract in Proceedings of ICALP 2006, pp 346-357 | 3-540-35904-4 |
Citations | PageRank | References |
28 | 2.53 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Parikshit Gopalan | 1 | 1186 | 61.52 |
| Phokion G. Kolaitis | 2 | 2733 | 514.37 |
| Elitza Maneva | 3 | 390 | 24.97 |
| Christos H. Papadimitriou | 4 | 16671 | 3192.54 |