サーキットの計算量の様々なクラス その1

一難去ってまた一難といった様相を見せる私の立場。台風のあとは相場が大荒れで、といっても貧乏な私にはあんまり関係ないはずのですが、最近ほんのちょっぴり勉強がてら投資したら、もう下がるわ下がるわ、びっくりするほど下がり続けて、本当に良い勉強になっている今日この頃。やっぱり秋は学問の秋ですかねえ。え、なんかちがいますか。

さて、前節では、基本的に二分木の場合を前提としていました。実は私も忘れていたのですが、「サーキットというグラフ　その1」にて、サーキットの定義として以下のことを書いているのでした。

【サーキットの定義】
　いま、ブール変数x1 , … , xnが与えられているとします。グラフは、無サイクルな有方向グラフであり、
　　
　　（１）すべてのノードのインデグリーは0、もしくは、2である
　　　　（１－１）インデグリー0のノードをインプットもしくはリーフと呼ぶ
　　　　　　　　　（一般に、入力であるブール変数x1 , … , xn が相当する）
　　　　（１－２）インデグリー2のノードはゲート（gate）と呼ばれ
　　　　　　　　　∧（論理積）もしくは∨（論理和）が付加されている
　　（２）アウトデグリーの値は任意であるが、アウトデグリー0のノードが
　　　　　ただ一つだけあり、このノードのことをアウトプット(output)と呼ぶ
　
以上を満たすものをこれから、ブール変数x1 ,…, xn 上のブーリアン・サーキット（Boolean circuit）または、単にサーキットと呼ぶことにします。

何せ、ソチオリンピックよりも前のこと。忘れていても仕方ないですが、もうすぐ一年にもなろうとしていますから月日の経つのは本当に早いですね。


さて、今回からは、このインデグリーが0か2という制限を外していろんなインデグリーの数の場合のことを考えていくことになります。即ち、一つのゲートの論理式が

もしくは

　


ということもあるということです。こうしたとき、バイナリーサーキットから上の形式のノードをいくつか用いる形で書き直すこともできます。そのようにして論理式Fを書き直してできる同様の論理式をF'としたときもリーフの数は変わりませんので

　L(F)=L(F')

となりますね。このように途中のノード（ゲート）を集約してもしてもサイズ（リーフの数や深さ）は変わらないのが一般的です。そこができるのであれば、そもそもの論理式に無駄があったということになります。

余談ですが、主に電子回路ではこのようなノードのことをゲートと呼びます。すなわち、真であれば電流が流れ、あるいは電圧が印加される部分の関門というイメージだと思われます。以下、テキストも拡張したゲートをノードと区別せずに単にゲートと呼んでいますので、ややこしいですがこの節では、それらも単にゲートと呼ぶことします。

さて、今言ったことをもう少し数学的に考えてみましょう。


サイズs:サーキットCがあったときのCのサイズとし,Cの中のゲート数をs(C)という形で表わす


というように定義します。

このとき、当然s(C)≠L(C)ですが、かりにサーキットCが二分木のようなバイナリーサーキットであるとすれば、

　s(C)=L(C)-1

として定義できるのはちょっと考えれば分ります。面白いので是非ご自分で考えて下さいね。

さらにサーキットCは論理式Fと等価であることからs(C)はs(F)という形でも表わされ、当然、

　s(F)=L(F)-1

となります。

今回はこのあたりで。

次からは本格的にクラスの定義に入っていきます。