- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Knowledge Graph Search feature is available on CiNii Labs
- 【Updated on June 30, 2025】Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
An exact algorithm for the Boolean connectivity problem for k-CNF
Bibliographic Information
- Other Title
-
- 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
Search this article
Description
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
-
- Theoretical Computer Science
-
Theoretical Computer Science 412 (35), 4613-4618, 2011-08
Elsevier B.V.
- Tweet
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
- Crossref
- CiNii Articles
- KAKEN
- OpenAIRE