CNFSATからHornSATへの変換手法について

• Item type: Trans(1)
• 公開日: 2011-09-22
• タイトル: CNFSATからHornSATへの変換手法について
• タイトル / 言語: en
• タイトル: The Method That Reduce CNFSAT to HornSAT
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 発表概要
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: フリー
• 著者名: 小林, 弘二
• 著者名(英): Koji, Kobayashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本発表では CNFSAT を HornSAT に帰着させる手法について述べる．HornSAT は P 完全問題であり，その充足可能性に関して項どうしが半順序構造を持つという優れた特長を持つ．そのため，HornSAT の各項の影響は局所的となり，コンピュータなどでの取扱いが容易となっている．しかし，CNFSAT は NP 完全問題であり，（CNF の構成によっては） CNF の充足可能性について，ある項が他の項と相互に依存するという構造を持つことがある．そのため，CNFSAT の各項の影響は局所的にはならない．その影響は CNF 全体に及ぶこともあり，結果として CNFSAT を HornSAT に置き換えることを難しくしている．本発表では CNFSAT の構造を HornSAT に置き換えるために，CNF の項どうしの関係に着目した．項どうしの関係は，大きく 2 つに分けることができる．1 つは同じ肯否を持つ変数を共有する関係であり，もう 1 つは異なる肯否となる同じ変数を共有する関係である．これら 2 つの関係それぞれに対応する HornSAT の項を作成し，その制約で CNFSAT の項の関係を構築することで CNFSAT から HornSAT への帰着を実現する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This presentation talks about the method to reduce CNFSAT to HornSAT. HornSAT is P-complete. And HornSAT have the feature that's clause have partial order in satisfiability. So HornSAT's clause affects locally, and computer can treat HornSAT easily. But CNFSAT is NP-complete. And CNFSAT's clause affects each other and affects all CNF clauses. And the feature makes it difficult to reduce CNFSAT to HornSAT. This presentation focuses attention on the relation of the CNFSAT's clauses to reduce CNFSAT to HornSAT. CNFSAT's clauses relations are two types. One is the relation between same variable and same positive/negative relations. One is the relation between same variable but different positive/negative relations. To create the HornSAT's clauses those have same constraint of the CNFSAT's clause relations, I get the HornSAT that reduce from CNFSAT.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 4, 号 4, p. 45-45, 発行日 2011-09-22
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会