On the Boolean connectivity problem for Horn relations
On the Boolean connectivity problem for Horn relations
复制标题
Horn关系的布尔连通性问题
DOI：
10.1016/j.dam.2010.08.019
复制
发表时间：
2010
影响因子：
1.1
通讯作者：
and M. Yamamoto
中科院分区：
文献类型：
--
作者：
K. Makino;S.Tamaki;and M. Yamamoto
Gopalan等人[P. Gopalan，P.G. Kolaitis，E.N. Maneva，C.H. Papadimitriou，布尔可满足性的连通性：计算和结构二分法，在：第33届自动机，语言和编程国际学术讨论会论文集，ICALP 2006年，2006年，pp。346-357]和[P. Gopalan，P.G. Kolaitis，E.N. Maneva，C.H. Papadimitriou，布尔可满足性的连通性：计算和结构二分法，SIAM J. COMPUT。38（6）（2009）2330-2355]的布尔公式的解空间的连通性性质，并在Schaefer的框架中研究了连通性问题的复杂性问题。一个逻辑关系集合S是Schaefer，如果S中的所有关系都是双连接的、Horn的、对偶Horn的或仿射的。他们首先指出，连接问题的谢弗是在P.我们反驳他们的猜想表明，存在一组S角的关系，使连接问题的S是coNP-完全的。我们还调查了一个易于处理的方面霍恩和双霍恩关系的特征集。
Gopalan et al. studied in [P. Gopalan, P.G. Kolaitis, E.N. Maneva, C.H. Papadimitriou, The connectivity of Boolean satisfiability: computational and structural dichotomies, in: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, 2006, pp. 346–357] and [P. Gopalan, P.G. Kolaitis, E.N. Maneva, C.H. Papadimitriou, The connectivity of Boolean satisfiability: computational and structural dichotomies, SIAM J. Comput. 38 (6) (2009) 2330–2355] connectivity properties of the solution-space of Boolean formulas, and investigated complexity issues on the connectivity problems in Schaefer’s framework. A set S of logical relations is Schaefer if all relations in S are either bijunctive, Horn, dual Horn, or affine. They first conjectured that the connectivity problem for Schaefer is in P. We disprove their conjecture by showing that there exists a set S of Horn relations such that the connectivity problem for S is coNP-complete. We also investigate a tractable aspect of Horn and dual Horn relations with respect to characteristic sets.