単調DNFの双対性判定問題

アルゴリズムFK
はじまるよ

アルゴリズムFKとは


はじめに
単調DNFと単調CNF
等価性判定と双対性判定
アルゴリズムFK

今度のアプローチ


考えるべきこと
ハイパーグラフ
木分割

参考文献



はじめに
アルゴリズムFKとは
単調DNFの双対性判定アルゴリズムで、現在最も効率の良いとされてい
るもの
実行時間は n
1o 1log n / log log n
単調DNFと単調CNF

DNF（Disjunctive Normal Form, 選言標準形）
(x1∧x2∧…∧xk) ∨ (xk+1∧xk+2∧…) ∨…

CNF（Conjunctive Normal Form, 連言標準形）
(x1∨x2∨…∨xk) ∧ (xk+1∨xk+2∨…) ∧ …
単調・・・否定を含まない
等価性判定と双対性判定
（問題）
二つの否定を含まない（単調な）ブール式が等価であるか？
・単調DNFと単調DNFの場合
与えられた単調DNFに対しては
それと等価な最小のDNFが一意に決まり、
それは容易に求められる
↓
二つの単調DNFの等価性の判定は容易
・単調DNFと単調CNFの場合
（素朴な方法）
単調CNFを分配則によって展開、整理
↓
単調DNFと比較
このアルゴリズムの最悪の実行時間は指数的
→見方を変えてみる
→二つの単調DNFの
双対性判定問題とみなす
二つの論理関数
f(x1,x2,…,xm)とg(x1,x2,…,xm)が互いに双対
→ f x1 , x2 ,, xm   gx1 , x2 ,, xm 
A…単調DNF
B…単調CNF とする
BのANDとORを入れ替えてできる
DNFをB’とおく
ドモルガンの定理より
BとB’は互いに双対
↓
AとB’が等価 = AとB’が双対
つまり、この問題は「単調DNFの双対性判定問題」と呼べる
これはさらに短縮して
「単調双対性問題（monotone duality）」
とも呼ばれる
アルゴリズムFK
単調双対性問題に多項式時間アルゴリズムは存在するか？
多項式時間のクラスに属するか、coNP完全であるかは未解決
FredmanとKhachiyanによって
no(log n/log log n)時間
のアルゴリズムが発表
→アルゴリズムFK
アルゴリズムFK
詳しい内容は省略させてください m(_ _;)m
でも簡単に説明すると・・・
問題 DUALITYを考える
入力単純な集合族の対(F, G)
問い ClFとClGは互いの双対か？
ここで、
ClF…Fの閉包
ClF = ｛J ⊆ [m] | ∃I∈F : I⊆J
ClF = ｛J ⊆ [m] | ∃I∈F : I⊆J}
[m] ・・・ m以下の正整数の集合
ex) [3]={1,2,3} [5]={1,2,3,4,5}
たとえば
m=3 F={{1}{1,3}{2,3}}のとき
ClF={{1}{1,2}{1,3}{2,3}{1,2,3}}
集合族FはDNFを通じて
fF(x1,x2,…,xm) = ∨∧xi
I∈F i∈I
のような単調論理関数fFを表現する
実は
ClFとClGが互いに双対であればfFとfGも互いに双対だといえる
↓
問題 DUALITYを解けば
単調DNFの双対性判定問題が解ける
ClFとClGが互いの双対
↓
(1)交差条件
C|Gの要素がすべてFの横断集合（transversal）
これは、Gの要素がFの横断集合であることと同値
(2)網羅条件
Fの横断集合すべてがC|Gに属する
ここで、Fの横断集合とは
すべてのJ∈Fで、I∩J≠φであるようなIのこと
ex) m=3 F={{1}{1,3}{2,3}}のとき
{1,2} {1,3} {1,2,3}がFの横断集合
交差条件は判定が容易
→主に網羅条件を判定する
それをうまくやったのがアルゴリズムFK
今後のアプローチ

木分割の幅が小さいような
ハイパーグラフについて能率のよい方法を考
える
ハイパーグラフ

グラフ
点の集合と辺の集合によってできている
通常のグラフの辺は２点によって表す
ex) V={1,2,3} E={{1,2}{1,3}}

ハイパーグラフ
点の集合と辺の集合によってできている
しかし辺に含まれる点は２つとは限らない
ex) V={1,2,3} E={{1}{1,3}{1,2,3}}
木分割
木である
 葉頂点の集合がグラフGの辺集合と等しい
 内部頂点の次数が３以下

参考文献

バイバイ♪
終わりなの
単調DNFの双対性判定問題Duality Testing of Monotone DNFs
（玉木久夫）

Download Report