An exact algorithm for the Boolean connectivity problem for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:mi>k</mml:mi></mml:math>-CNF

DOI DOI 機関リポジトリ (HANDLE) HANDLE Web Site ほか1件をすべて表示 一部だけ表示 被引用文献11件 参考文献17件 オープンアクセス

書誌事項

タイトル別名
  • An exact algorithm for the Boolean connectivity problem for k-CNF

この論文をさがす

説明

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.

収録刊行物

被引用文献 (11)*注記

もっと見る

参考文献 (17)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ