Journal
THEORETICAL COMPUTER SCIENCE
Volume 412, Issue 35, Pages 4613-4618Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2011.04.041
Keywords
Exponential-time algorithms; Boolean connectivity; CNF satisfiability
Categories
Funding
- Grants-in-Aid for Scientific Research [23700015, 22240001] Funding Source: KAKEN
Ask authors/readers for more resources
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 O((2 - epsilon(k))(n)) for some constant epsilon(k) > 0, where epsilon(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 - epsilon)(n)) for any constant epsilon > 0, provided that the SAT problem (with no restriction to the clause length) is not solvable in time O((2 - epsilon)(n)) for any constant epsilon > 0. (C) 2011 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available