単調な3乗法標準形論理式に対する真理値割当て全体の整列可能性と2次元の間接的2分探索アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2017-09-12
• タイトル: 単調な3乗法標準形論理式に対する真理値割当て全体の整列可能性と2次元の間接的2分探索アルゴリズム
• タイトル / 言語: en
• タイトル: Sortability of the Set of All Truth Assignments for a Monotone 3-Conjunctive Normal Form Formula and a 2-Dimensional Indirect Binary Search Algorithm
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 青山学院大学理工学部情報テクノロジー学科
• 著者所属(英): en
• 著者所属(英): Department of Integrated Information Technology, College of Science and Engineering, Aoyama Gakuin University
• 著者名: 松原, 俊一
• 著者名(英): Shunichi, Matsubara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿ではまず，与えられた正の 3CNF 式について，真理値割当ての符号語全体が 2 次元で整列するような正の 3CNF 式を構成できることを示す．次にこの符号語全体から 2 次元の 2 分探索法を示す．真理値割当ての符号語全体は，入力の指数サイズとなるが，提案法では一部の符号語を必要に応じて構成する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we first show that given a positive 3CNF formula ψ, we can find an equivalent positive 3CNF formula φ such that the binary representations of all truth assignments of φ can be sorted. Then, we propose a kind of 2-dimensional binary search algorithm for deciding whether there is a satisfying assignment in the sequence. Representing the whole sequence requires an exponential space for the size of the given formula ψ. The proposed algorithm searches a target value without constructing all the binary representations of the sequence.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2017-AL-164, 号 5, p. 1-3, 発行日 2017-09-12
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会