An exact algorithm for the Boolean connectivity problem for k-CNF
An exact algorithm for the Boolean connectivity problem for k-CNF
复制标题
k-CNF 布尔连通性问题的精确算法
DOI：
10.1016/j.tcs.2011.04.041
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
M.Yamamoto
中科院分区：
文献类型：
--
作者：
K.Makino;S.Tamaki;M.Yamamoto
我们给出了一个求解PSPACE-Complete问题的精确算法，称为CONNkSAT，它询问给定的k-CNF公式的解空间在n维超立方体上是否连通。这个问题对于k≥3是空间完备的，对于k≤2是多项式可解的(Gopalan等人，2009年)[6]。证明了k-≥3的ConnkSAT对于某个常数ϵk>；0在时间上是可解的[公式：见文]，其中ϵk只依赖于k，而不依赖于n.这一结果被认为是有趣的，因为如下事实：QBF-3-SAT是一个典型的ϵ-3-SAT问题，对于任何常数ϵ>；0，QBF-3-SAT在时间O((2−ϵ)n)上是不可解的，如果对于任何常数ϵ>；0，SAT问题(对子句长度没有限制)在时间O(2 PSPACE)n上不能解；0。
We present an exact algorithm for a PSPACE-complete problem, denoted by CONNkSAT, which asks whether the solution space for a given k-CNF formula is connected on the n-dimensional hypercube. The problem is known to be PSPACE-complete for k≥3, and polynomial solvable for k≤2 (Gopalan et al., 2009) [6]. We show that CONNkSAT for k≥3 is solvable in time [Formula: see text] for some constant ϵk>0, where ϵkdepends only on k, but not on n. This result is considered to be interesting due to the following fact shown by Calabro [5]: QBF-3-SAT, which is a typical PSPACE-complete problem, is not solvable in time O((2−ϵ)n) for any constant ϵ>0, provided that the SAT problem (with no restriction to the clause length) is not solvable in time O((2−ϵ)n) for any constant ϵ>0.