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

おはようございます。昨日は疲れから少々早めに寝てしまい、その分少し早めに目が覚めてこの記事を書いているのですが、やっぱり夜遅くやるよりは少し寝てからの方が良いですね。でも目をつむっているだけでも十分であるとかないとか。何となくが何となく良い感じであるのはなんとなくですが良い感じですね。それにしても、テキストにはいろんな文字が使われていまして、似ている文字を選んできて使用するというのも一苦労なんですよ。今回近似サーキットを扱っていますが、近似サーキットの記号を近似させるのにも一苦労ってどういうことなんでしょうかねえ、ふう。


さて、今日は前回の定理を用いて近似サーキットの定義をしていきます。

まず、

　　m=(p-1)^l・l!

とおきます。ここでlは濃度ですがpはよりも大きい整数です。こうしておくと、花つみが終了すればクリーク表示の数は<2m(「モノトーンそしてmP≠mNP その4」参照）から≦mとなるのが分ると思います。

【論理和型近似サーキットの定義】
つまり、「モノトーンそしてmP≠mNP その4」で考えていた、C=C1∨C2の近似サーキットC'1＝A,C'2＝Bとして表わし、それぞれの花つみが終わっってクリーク表示の数が≦mなったものを∨で結んだものを

　　AЦB

と表わすことにし求める近似サーキットであると定義します。


次に論理積型の近似サーキットを考えていきます。

論理和型と同様にC=C1∧C2において、近似サーキットC'1＝A,C'2＝Bとして表わし、論理和型と同様に
　
　　C'1＝A=┌X1┐∨┌X2┐∨…∨┌Xr┐,　C'2＝B=┌Y1┐∨┌Y2┐∨…∨┌Ys┐

となっているとします。このとき、C=C1∧C2は、
　　　　　　　　　

となり、ここで┌Xi┐∧┌Yj┐はクリーク表示ではなく、また個数も≦m^2であるのは明らかで、これは花つみをしてもmより大きいかもしれないという可能性があります。

【論理積型近似サーキットの表記と求め方】

まず、求める論理積型の近似サーキットを
　
　AПB

と表記することにします

その求め方として以下の手順を採用します

(1)┌Xi┐∧┌Yj┐を┌Xi∪Yｊ┐に書き換えます。

　※テキストには説明ありませんが、┌Xi┐∧┌Yj┐が真ならば┌Xi∪Yｊ┐は必ずしも真ではありませんが、┌Xi∪Yｊ┐が真ならば┌Xi┐∧┌Yj┐は必ず真であるため置き換えることが可能だということだと思われます。


(2)もし|Xi∪Yｊ|>lならばXi∪Yｊは真となりますので、┌Xi∪Yｊ┐を消します

(3)そのようにした上で花つみを行いAПBを得る

という事になります。



次回からは、以上で完成した近似サーキットについての三つの補題を順に説明していくことになります。