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

しかし、どうしていじめというのは無くならないんですかね。私もんＨＫのいまはあれであれをああし続けてどうしているのか不明の方にタコだとか何とか言い続けられましたが、別にくねくねしたくてしているわけでも無し、なんでそういうことを言うかな、と思うわけですよ。要するに、気に入らないからといって何をしても良いと思っている人もたくさんいらっしゃって、こちらに原因がないとは言いきれないとは思いますがねえ。


　さて、計算量のクラスとしてNC^i、AC^iの説明に入りたいと思います。実は、

　NC^i


は


　


と

　AC^iは


　


と表記するのですが、これからたびたび説明で使う関係上、その度に図で表記するのも煩雑なのでNC^i、AC^iという表記を使わせて頂きたいと思います。多少見にくいですがどうぞご了承下さい。


まずは定義から

【NC^i,AC^iの定義】

ユニフォームなサーキットの族{C1,C2,…}で、多項式のサイズや深さが




で、NC^iはインデグリーが定数で抑えられているもの。AC^iは、インデグリーに制限のないもので計算されるブールの族。

［用語の解説］
※族：数学における族（ぞく、family）は、添字付けされた元（要素）の（一般には非可算無限個の）集まりで、対、n-組、列などの概念の一般化である。系（けい、collection）と呼ぶこともある。元がどのような対象であるかによって、点族、集合族（集合系）、関数族（関数系）などと呼ばれる。
　　（Wikipedia（http://ja.wikipedia.org/wiki/族_(数学)より引用））

※ユニフォーム：定義としては、ある種の族{C1,C2,…}で表わされたサーキットや論理式などを自然数に置換し、置換した自然数を再び同じ族で表わすことができるとする。このとき

　f(i)=Ci　

という関数があって、それをクラスAC^0で表わすことができるもの



今回はもう少しこの定義について解説したあと、次回以降、それぞれのクラスの包含関係などの考察に入ります。

今まで考察してきたもののサイズや深さはO(log n)でした。即ちこれが現時点ではもっとも一般的に有用なグラフといえるかもしれません。ところが、これはいま平面上にサーキットがあったから、そうだとも言えます。これが立体面であれば、オーダーはこの自乗になるのは自明です。そのように次元を上げていった場合などを一般化して扱うのが数学とも言えます。そういうわけで今回は、



の場合、すなわちNC^i,AC^iの場合も考察してみようということになるわけです。