単調双対性問題 Monotone Duality 明治大学理工学部情報科学科４年奥澤正輝背景  単調双対性問題（monotone duality）＝「単調DNFの双対性判定問題」単調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と比較 ↓ 等価であるか判定このアルゴリズムの最悪の実行時間は指数的 →ならば、どうするか？ためしに、このアルゴリズムでCNFをDNFに変換してみる x  x ○ x  x ○ x x  ○ 1 2 1 3 4 5 x1 x4  x1 x5  x1 x3 x4  x1 x3 x5  x1 x2 x4  x1 x2 x5  x2 x3 x4  x2 x3 x5 x1 x4  x1 x5  x2 x3 x4  x2 x3 x5 ○○ ○○ はtransversal（横断集合）である x1 x5、 x2 x3 x4、 x2 x3 x5 も、transversal →DNFはCNFのtransversalの集合つまり、CNFのtransversalをすべて見つけ出してそれらの和集合を求めれば、それは、そのCNFと等価なDNFとなる。 →これを利用したアルゴリズムを考える DUALIZE 入力：単調CNF 出力：単調DNF 入力した単調CNFを単調DNFに変換して出力する Step1: tmin（最小のprime implicant）を求めて Qに代入 Step2: while( Q   ) do begin Qの中で最小の項をoutputに追加 tにその項を入力し、Qから削除 for( xi V t  & &i t   1となるようなiそれぞれに対して) do begin 力ずくで i t  をρ(t, i)（prime DNF）に変換 for(ρ(t, i)に含まれるt’それぞれに対して) do begin if( t i 1  t ' がfiのprime implicantである) do begin 最小のprime implicant t*を求める（ti* = t i 1  t ' ） Qに Q  t * を代入 end{if} end{for} end{for} end{while} 考え方まず、横断集合をひとつ求める。 transversal：○○○○○○ ここで、横断集合は左からindexの小さい順であるとする。 ↓ これをもとにして横断集合を求めるわけだが、次のようにする。考え方 transversalのある要素xiに対して、indexがそれより大きいもの（小さいもの）を省く。 xi／／／ ○○○○○○ 残ったものに、ある要素よりindexが大きいもの（小さいもの）を加えて新しいtransversalをつくる。 ○○○○○ これをtransversalの要素すべてに対してindexの小さい順に行う。 ↓ こうしてできたtransversalに対して同じことを繰り返す。 ↓ こうやってtransversalを次々生成してDNFを求める。例）↓のようなCNFの横断集合を求める x1  x2 x1  x3 x4  x5  まず、力ずくで x2 x3 x5 を見つける。これをもとに他の横断集合を見つける。 x5 を x4 に変えて x2 x3 x4 x2 x3　を x1に変えて x1x5 これらをもとに他の横断集合を見つける。 x1 x5 の x5 を x4 に変えて x1 x4 x x  x x  x2 x3 x4  x2 x3 x5 こうしてDNF 1 4 1 5 が求められた。 (ms) 5000 4800 4600 4400 4200 4000 3800 3600 3400 3200 3000 2800 2600 2400 2200 2000 1800 1600 1400 1200 1000 800 600 400 200 0 実行時間 DUALIZE 力ずく双対性判定ここまでは、単調DNFと単調CNFの等価性問題を解くのに単調CNFを単調DNFに変換してから、２つの単調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と単調CNFの等価性判定問題は単調DNF同士の双対性判定問題＊）として考えることができる。＊）短縮して、「単調双対性問題（monotone duality）」とも呼ぶ。単調DNFの双対性判定アルゴリズムで現在最も効率の良いとされているものアルゴリズムFK（FredmanとKhachiyan）実行時間は n 1o 1log n / log log n 双対性問題が多項式時間クラスに属するのかcoNP完全であるのかは解決していないが、coNP完全である可能性は少ないと見られている。今後の目的単調双対性問題は特別な場合のみ多項式時間で解けるものがいくつか知られている。（２単調関数、マトロイド関数など）特別な場合に限らない、多項式時間アルゴリズムの可能性を探る。手近な課題木分割の木幅の小さいhypergraphについて能率のよい方法を考える →そこからアルゴリズムFKの改良につながるかも？＊）すでに木幅がk以下であるCNF については（kがconstantのとき） O ・ n2k 1 　＊）  は のindexの総数（k= Ologlog   のとき）多項式時間で解けることが知られている。 →これを改良する。参考文献  NEW RESULTS ON MONOTONE DUALIZATION AND GENERATING HYPERGRAPH TRANSVERSALS （Thomas Eiter, Georg Gottlob, Kazuhisa Makino）