An exact algorithm for the Boolean connectivity problem for k-CNF

We present an exact algorithm for a PSPACE-complete problem, denoted by , 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 for k≥3 is solvable in time O((2−ϵk)n) for some constant ϵk>0, where ϵk depends 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.