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

HANDLE Open Access

Search this article

Abstract

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).We show that CONNkSAT 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: 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.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

  • CRID
    1050564285674339968
  • NII Article ID
    120003338848
  • NII Book ID
    AA00862688
  • ISSN
    03043975
  • HANDLE
    2433/145991
  • Text Lang
    en
  • Article Type
    journal article
  • Data Source
    • IRDB
    • CiNii Articles
    • KAKEN

Report a problem

Back to top