モノトーンそしてmP≠mNP その4

おはようございます。おめでとうございます。土曜も日曜もなくくるくると回っております～。私の頭の中以外、何がおめでたいのか分りませんが。とりあえず、今日から十一月ですので、元気よくやってみました。


さて、今回から数度に分けて、サーキットに近似サーキットを適用していくやり方を説明していきます。考え方としてはサーキットをリーフから部分、部分に分けて近似サーキットに置き換えていくという考え方です。

そういうわけで、まずリーフから。

 (i) 枝{i,j}を持つリーフをのインプットのブール変数をxijと表記するとした場合、i≠j)┌{i,j}┐を近似サーキットと定義する

次に、C=C1∨C2の時を考えます

 (ii)C=C1∨C2で近似サーキットC'1,C'2が以下のように近似サーキットの論理和ですでに結ばれているとき
　　　
　　　C'1=A=┌X1┐∨┌X2┐∨…∨┌Xr┐,　C'2=B=┌Y1┐∨┌Y2┐∨…∨┌Ys┐

これを論理和で結ぶと　　　

┌X1┐∨┌X2┐∨…∨┌Xr┐∨┌Y1┐∨┌Y1┐∨┌Y2┐∨…∨┌Ys┐

となり、r+s個のクリーク表示を論理和∨で結んだものになるためr+s≦2mである事は言えるが、r+s≦mは満たさないかもしれず、すなわち、リーフをはじめノードのサイズが元と同じにならないかもしれません。そのために次のようなことを考えます。


【ヒマワリと花つみ】
　いま相異なる集合Z1,Z2,…,Zpで、Zi∩Zjがすべてのi≠jについて等しいとき、Z1,Z2,…,Zpを中心Zi∩Zjをもつヒマワリと呼びます

また、ある数p≧2を定めて、現在問題になっているノード集合の集合{X1,X2,…,Xr,Y1,Y2,…,Ys}を見ます。そのとき、もし、X1,X2,…,Xr,Y1,Y2,…,Ysの中でp個の集合がヒマワリを作っているとすれば、そのp個のノード集合をそのヒマワリの中心で置き換える、という事にします。この操作を花つみと呼ぶことにします。花つみは常にこれ以上できなくなるまですることにします。頂点の数は花つみをするたびに減りますので、高々2m回の花摘みしかできない、という事になります。

これに関する補題（ある定理の中のサブ定理のことを補題と言います）がありますが、少し難しいのでそれはまた次回説明することにしましょう。