ログイン 新規登録
言語:

WEKO3

  • トップ
  • ランキング
To
lat lon distance
To

Field does not validate



インデックスリンク

インデックスツリー

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. 研究報告
  2. アルゴリズム(AL)
  3. 2025
  4. 2025-AL-201

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

https://ipsj.ixsq.nii.ac.jp/records/241900
https://ipsj.ixsq.nii.ac.jp/records/241900
c631fbe1-bc3b-4255-b910-a41810350e15
名前 / ファイル ライセンス アクション
IPSJ-AL25201012.pdf IPSJ-AL25201012.pdf (1.0 MB)
 2027年1月7日からダウンロード可能です。
Copyright (c) 2025 by the Information Processing Society of Japan
非会員:¥660, IPSJ:学会員:¥330, AL:会員:¥0, DLIB:会員:¥0
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

× Yuto, Okura

Yuto, Okura

Search repository
Junichi, Teruyama

× Junichi, Teruyama

Junichi, Teruyama

Search repository
Kazuhisa, Seto

× Kazuhisa, Seto

Kazuhisa, Seto

Search repository
Takashi, Horiyama

× Takashi, Horiyama

Takashi, Horiyama

Search repository
著者名(英) Yuto, Okura

× Yuto, Okura

en Yuto, Okura

Search repository
Junichi, Teruyama

× Junichi, Teruyama

en Junichi, Teruyama

Search repository
Kazuhisa, Seto

× Kazuhisa, Seto

en Kazuhisa, Seto

Search repository
Takashi, Horiyama

× Takashi, Horiyama

en Takashi, Horiyama

Search repository
論文抄録
内容記述タイプ 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
出版者 情報処理学会
戻る
0
views
See details
Views

Versions

Ver.1 2025-01-19 07:30:11.266921
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3