Exact Algorithm for the Boolean Connectivity of <i>k</i>-Horn Formulas via Deterministic PPZ

• Item type: SIG Technical Reports(1)
• 公開日: 2025-01-07
• タイトル: Exact Algorithm for the Boolean Connectivity of <i>k</i>-Horn Formulas via Deterministic PPZ
• タイトル / 言語: en
• タイトル: Exact Algorithm for the Boolean Connectivity of <i>k</i>-Horn Formulas via Deterministic PPZ
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Hokkaido University
• 著者所属: University of Hyogo
• 著者所属: Hokkaido University
• 著者所属: Hokkaido University
• 著者所属(英): en
• 著者所属(英): Hokkaido University
• 著者所属(英): en
• 著者所属(英): University of Hyogo
• 著者所属(英): en
• 著者所属(英): Hokkaido University
• 著者所属(英): en
• 著者所属(英): Hokkaido University
• 著者名: Yuto, Okura; Junichi, Teruyama; Kazuhisa, Seto; Takashi, Horiyama
• 著者名(英): Yuto, Okura; Junichi, Teruyama; Kazuhisa, Seto; Takashi, Horiyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: The Boolean connectivity problem asks whether the satisfying assignments of a given Boolean formula are connected over the n-dimensional hypercube. Makino, Yamamoto, and Tamaki showed that this problem is coNP-complete even if a given formula is restricted to a 3-Horn formula. In this paper, we show that the deterministic PPZ algorithm presented by Paturi, Pudlak, and Zane can solve the Boolean Connectivity of a given k-Horn formula over n variables in time O*(2(1-1/2k)n). It can also count the number of the connected components of satisfying assignments.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The Boolean connectivity problem asks whether the satisfying assignments of a given Boolean formula are connected over the n-dimensional hypercube. Makino, Yamamoto, and Tamaki showed that this problem is coNP-complete even if a given formula is restricted to a 3-Horn formula. In this paper, we show that the deterministic PPZ algorithm presented by Paturi, Pudlak, and Zane can solve the Boolean Connectivity of a given k-Horn formula over n variables in time O*(2(1-1/2k)n). It can also count the number of the connected components of satisfying assignments.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2025-AL-201, 号 12, p. 1-4, 発行日 2025-01-07
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会