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 |
|
収録物識別子 |
AN1009593X |
書誌情報 |
研究報告アルゴリズム(AL)
巻 2025-AL-201,
号 12,
p. 1-4,
発行日 2025-01-07
|
ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |