| 講演抄録／キーワード |
| 講演名 |
2006-03-23 14:30
種々の制限を加えたTree-Shellable論理関数判定問題の複雑さ
○加藤木 直・武永康彦・石橋 尚（電通大） |
| 抄録 |
（和） |
Tree-Shellable論理関数とは、根のノードから1にラベル付けされた葉ノードへのパスの数が、主項の数と同じようになるような二分決定木表現をもつ正論理関数である。また二分決定木が順序付きであるならば、Ordered tree-shellable論理関数であるという。
本稿では、関数内の積項に含まれるリテラルの最大数が4以上の場合、ordered tree-shellable論理関数判定問題はNP完全問題であることを明らかにする。また同一変数の出現回数に制限を加えた場合の(oredered) tree-shellable論理関数判定問題の性質を明らかにし、その結果より(oredered) tree-shellable論理関数判定問題の計算複雑さを明らかにする。 |
| （英） |
A tree-shellable function is a positive Boolean function which can be represented by a binary decision tree whose number of paths from the root to a leaf labeled 1 equals the number of prime implicants.
In this paper, we show that it is NP-complete to check the ordered tree-shellability even if the maximum number of literals in a term is 4. We also consider the property of tree-shellable funcitons when the number of the same literal in the DNF is restricted. |
| キーワード |
（和） |
tree-shellability / 論理関数 / 二分決定木 / 主項 / / / / |
| （英） |
tree-shellability / Boolean function / binary decision tree / prime implicant / / / / |
| 文献情報 |
信学技報, vol. 105, no. 680, COMP2005-67, pp. 31-37, 2006年3月. |
| 資料番号 |
COMP2005-67 |
| 発行日 |
2006-03-16 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|