ノンモノトーンで計算が減る場合 その1

おはようございます。日本料理がユネスコの無形文化遺産に晴れて登録され認定書が渡されたというニュースがありましたが、日本食の素材の良さを生かすも殺すも包丁さばき。元々、良く切れる刃物があったことも日本食には重要だったのかもしれないなともおもいます。立派な料理人さんや包丁とは違いなかなか切れない頭とほどほどとも言いがたい腕の私ですが、この大変といえば大変で私には立派すぎる素材をなんとか綺麗に切り分けてみたいものです。

さて今回は、ノンモノトーン・サーキットの計算量が減る場合に関してブール代数的な表現とその定理の証明をします。

まず、前回(「モノトーンそしてmP≠mNP その12」）、テキストから引用した竹内先生のアイディアを再掲したいと思います。

「まずアイディアを説明する。a1,…,anを相異なった元とする。このとき集合Aが{a1,…,an-1}であるか{a1,…,an-2,an}であるか,……または{a2,…,an}であるかであるか?という命題を考える。いま{a1,…,ǎi,…,an}をa1,…,anからaiを抜いた元の集合を表わすものとすれば、上のAは{a1,…,ǎi,…,an}のi=1,…,nのどれかということになる。ここで表わされるaの数はn(n-1)である(注：n個の元をとり、それをチェックするのにはn(n-1))。これをAは{a1,a2,…,an}からa1を取ったものかa2を取ったものか、……またはanをとったものかといえば、aの表わされる数は2n（注：取り出す組み合わせがnチェックにn）とすくなくなる」

では、ブール代数的に表現した式(formula)ではどうなるのかというと

(※注：フォントセットの都合上テキストでxとあるものをzを用いています。以下同様)

　　※ここでyiは任意のチェックのために必要なブール代数


とする。ここでi,jは1,2,…,nを走るとテキストにはあります。この場合、式のサイズ(以下formula size)という概念で考えると、

　(1)はn(n-1)/2+n^2

　(2)はn(n-1)/2+3n

という形になりオーダーこそ同じものの確かにサイズが減っています。

このことを即ち

【定理】(1)と(2)は同等である

として証明していきます

【証明】

上式（１）、（２）の

　　

の部分とは独立に

　　




　すなわち

　　


を仮定し、この仮定のもとで、次の二式が同等であるということを言えば良いわけです

　
　　　

まず、(＊)より(z1∨…∨ži∨…∨zn)から(z1∨…∨zn)∧￢ziが出ることをいいます。

(＊)からまず、　

　　　z1∨…∨ži∨…∨zn→￢zi

　を出すことができます。これから　
　　
　　　z1∨…∨ži∨…∨zn→(z1∨…∨zn)∧￢zi

　を出すことができます。

また、

　(z1∨…∨zn)∧￢zi→z1∨…∨ži∨…∨zn)∧￢zi

　　　　　　　　　　　　　　→　z1∨…∨ži∨…∨zn

というのは自明です。

これから、つぎの3つの式が同等であると言うことが分かります


　

　

以上で証明が終わりました。

次回は、この定理から、私が考えたことを説明したいと思います。