A Computational Trichotomy for Connectivity of Boolean Satisfiability
A Computational Trichotomy for Connectivity of Boolean Satisfiability
复制标题
布尔可满足性连通性的计算三分法
DOI：
10.3233/sat190097
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Konrad W. Schwerdtfeger
中科院分区：
文献类型：
--
作者：
Konrad W. Schwerdtfeger
对于布尔可满足性问题，解空间的结构由解图来表征，其中顶点是解，并且两个解相连当且仅当它们在一个变量上完全相同。 2006 年，Gopalan 等人。主要受可满足性算法和可满足性阈值研究的启发，研究了 CSP 的解图的连通性属性和相关的复杂性问题。他们证明了连通分量的直径和 st-连通性问题的复杂性的二分法，并猜想了连通性问题的三分法。
在此工作的基础上，我们在这里证明了三分法：连通性要么是 P、coNP 完全，要么是 PSPACE 完全。此外，我们纠正了 Gopalan 等人的一个小错误，该错误导致边界稍微向硬侧移动。
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. In 2006, Gopalan et al. studied connectivity properties of the solution graph and related complexity issues for CSPs, motivated mainly by research on satisfiability algorithms and the satisfiability threshold. They proved dichotomies for the diameter of connected components and for the complexity of the st-connectivity question, and conjectured a trichotomy for the connectivity question.
Building on this work, we here prove the trichotomy: Connectivity is either in P, coNP-complete, or PSPACE-complete. Also, we correct a minor mistake of Gopalan et al., which leads to a slight shift of the boundaries towards the hard side.