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

およげたいやきくんではありませんが、まいにちまいにち、鉄板の穴の中でくるくると回されながら焼かれている気がしている今日この頃。今朝もくるくると早朝から働かせていただいております。

さて、今回はNC^iとAC^iの包含関係などを検討していくことになります。

テキストによると、このような議論をするときユニフォームとは限らないサーキットの族Cnが、多項式のサイズで深さが

であると考えます。

ところで、NC^iのインデグリーが定数で抑えられているのに対してAC^iはなんの制限もありませんので一般的に、

　NC^i⊆AC^i

であることは明らかです。

次に、NC^iのインデグリーを抑えている定数をcとするときインデグリーcのサーキットをインデグリーが0か2のバイナリーサーキットに置き換える事を考えると、このことは可能であることもサーキットのサイズsはlogc倍増えるであろう事は簡単に分ります。

ところで、

　AC^i⊆NC^i+1

を検討してみると、これは定義からして深さはO(log n)倍、サイズもこの記事の最初に定義したように多項式倍に増える、という事になるだけと言えます。

ここで、

　NC=∪NC^i,　AC=∪AC^i

とすると、以上より

　NC=AC

ということが言え、NCやACにはユニフォームという制限、即ち、自己言及可能であるという制限がついていますので

　NC=AC⊆P

が言えるということになります。すなわち、たいていのサーキットはチューリングマシンで計算可能であると言える、という事になります。

今回はここまでです。次回からはNCとACのユニフォームという制限を外した場合、即ちノンユニフォームなサーキットでの場合をしばらく考えるということになります。