種々の制限を加えたTree-Shellable論理関数判定問題の複雑さ
スポンサーリンク
概要
- 論文の詳細を見る
Tree-shellable論理関数とは、根のノードから1にラベル付けされた葉ノードへのパスの致が、主項の数と同じようになるような二分決定木表現をもつ正論理関数である。また二分決定木が順序付きであるならば、ordered tree-shellable論理関数であるという。本稿では、関数内の積項に含まれるリテラルの最大数が4以上の場合、ordered tree-shellable論理関数判定問題はNP完全問題であることを明らかにする。また同一変数の出現回数に制限を加えた場合の(oredered) tree-shellable論理関数判定問題の性質を明らかにし、その結果より(oredered) tree-shellable論理関数判定問題の計算複雑ぎを明らかにする。
- 2006-03-16
著者
-
加藤木 直
電気通信大学 電気通信学研究科 情報工学専攻
-
武永 康彦
電気通信大学 電気通信学部 情報工学科
-
石橋 尚
電気通信大学 電気通信学部 情報工学科
-
武永 康彦
電気通信大学電気通信学部情報工学科
-
武永 康彦
電気通信大学
関連論文
- 種々の制限を加えたTree-Shellable論理関数判定問題の複雑さ
- ナンバーリンクのNP完全性と問題の列挙
- D-1-2 「ストーンヘンジ」の先手必勝性と一般化ストーンへンジのPSPACE完全性(D-1. コンピュテーション,一般セッション)
- D-1-6 OBDDを用いた画像処理アルゴリズム(D-1. コンピュテーション,一般セッション)
- 多変量閾値関数の非明示的OBDD表現
- Chordal+k_1e-k_2eグラフの頂点彩色問題
- Coloring Comparability-ke Graphs(New Trends in Theory of Computation and Algorithm)
- 組合せ最適化問題としてのぷよぷよの連鎖数判定問題(計算量理論)
- リテラルの出現回数に制限を加えたTree-Shellable論理関数の判定複雑さ
- 比較可能+keグラフの彩色問題 (計算機科学基礎理論とその応用)
- 一般化ぷよぷよのNP完全性 (計算機科学基礎理論とその応用)
- 一般化ぷよぷよの連鎖数判定問題
- 比較可能+keグラフの彩色問題の計算量
- 一般化ぷよぷよの連鎖数判定問題
- 比較可能+keグラフの彩色問題の計算量
- D-1-9 区間グラフのOBDD表現について(D-1. コンピュテーション, 情報・システム1)
- 積項の長さに制限を付けた論理関数のOrdered Tree-Shellability (計算機科学基礎理論の新展開)
- ブロック化分岐プログラムにおける変数順序と表現能力の関係
- A-28 k回読みblockwise分岐プログラムについて(計算モデル,A.アルゴリズム・基礎)
- 杉原厚吉, 茨木俊秀, 浅野孝夫, 山下雅史(編), "アルゴリズム工学-計算困難問題への挑戦-", 共立出版(2001-06), A4変型判, 定価(本体4,800円+税)
- On Tree-Shellable Boolean Functions
- Tree-Shellable論理関数について
- Tree-Shellable倫理関数の判定複雑さ
- Tree-Shellable論理関数の判定の複雑さ (計算理論とアルゴリズムの新展開)
- Recognition of Ordered Tree-Shellable Functions Based on OBDDs (Algorithm Engineering as a New Paradigm)
- 幅に制限を加えたOBDDの等価性判定
- Recognizing Ordered Tree-Shellable Boolean Functions Based on OBDDs (Foundations of Computer Science)
- 二分決定グラフに基づくOrdered Tree-Shellable論理関数の判定
- 単調関数の最小二分決定グラフ推論問題のNP完全性
- トリックテイキングゲームの計算量と必勝戦略 (アルゴリズムと計算理論の新展開)
- 比較可能-keグラフの頂点彩色問題のパラメータ化計算量