2-CNFのシグネチャの列挙

• Item type: SIG Technical Reports(1)
• 公開日: 2024-05-01
• タイトル: 2-CNFのシグネチャの列挙
• タイトル / 言語: en
• タイトル: Generating Signatures of a 2-CNF
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 法政大学理工学部
• 著者所属: 法政大学理工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Engineering, Hosei University
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Engineering, Hosei University
• 著者名: 加藤, 志虎; 和佐, 州洋
• 著者名(英): Shitora, Kato; Kunihiro, Wasa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 節 ????1, . . . , ???????? と変数集合 ???? = {????1, . . . , ????????} を持つ CNF Φ が与えられたとき，変数への真理値の割当 ???? : ???? → {0, 1} は節の真理値の割当であるシグネチャ ????Φ (????) = (????1(????), . . . , ????????(????)) を導出する．ここで，???????? (????) = 1 となるのは ???? を代入することで ???????? の値が真となるときで，それ以外の場合は ???????? (????) = 0 である．Be'rczi ら [Be'rczi et al., TCS, 2021] は，tractable な CNF に対してフラッシュライトアプローチを用いることで，シグネチャを ????(???? · SAT) 遅延で列挙することができると証明した．ここで，SAT は入力の CNF の任意の部分 CNF に対して，それが充足可能かどうか決定するのにかかる時間計算量の上界である．ただし，このアルゴリズムは節を選ぶ際に毎回部分 CNF が充足可能であるか，スクラッチで計算しており，そこがボトルネックとなっていた．そこで，本研究では del Val[del Val, AAAI, 2002] のアルゴリズムを用いることで，入力を 2-CNF に限定した際に効率的に列挙できるアルゴリズムの構築を目指す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given a CNF Φ with variable set ???? = {????1, . . . , ????????} and clause set ????1, . . . , ????????, a variable assignment ???? : ???? → {0, 1} derives the assignment of clauses, called the signature, ????Φ (????) = (????1(????), . . . , ????????(????)). Here, ???????? (????) = 1 if and only if at least one literal ???? in ???????? holds that ????(var(????)) = 1. Be'rczi et al. [Be'rczi et al., TCS, 2021] show that all signatures in a given CNF can be enumerated in ????(???? · SAT) per sigunature if the CNF is tractable, that is, the satisfiability of any subset of the CNF can be solved in time polynomial. Here, SAT is the computational time for checking the satisfiability of such CNF. In this paper, by using a 2-SAT algorithm given by del Val [del Val, AAAI, 2002], we conjecture that if an input CNF is 2-CNF, the signature enumeration problem can be solved in time linear per solution on average.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2024-AL-198, 号 13, p. 1-5, 発行日 2024-05-01
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会