Computer Science – Computational Complexity
Scientific paper
2006-09-13
Extended abstract in Proceedings of ICALP 2006, pp 346-357
Computer Science
Computational Complexity
Scientific paper
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, small diameter and tractability 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.
Gopalan Parikshit
Kolaitis Phokion G.
Maneva Elitza
Papadimitriou Christos H.
No associations
LandOfFree
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-554364