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

おはようございます。「一粒で何度もおいしいこの冒頭の云々」と前回書いたところ非常に微妙な反応がありましたので、一粒で何度も微妙な味わいのあるこの冒頭のつかみの部分とお詫びして訂正させて頂きたいと思います。


さて、今回まではユニフォームのクラスについてもう少しお話しすることになります。

ここまで、論理式やサーキットの計算量のクラスがなんであるかと言うことを考えていましたが、今度は逆にクラスPをサーキットで表わすということについて考察していきます。

再びTM（チューリングマシンの略、以下同じ）のインプットがx、n=|x|として処理時間がt(n)、空間量がs(n)であるようなプログラムMの場合を考えます。

前にも言いましたが、プログラムはすべてコーディングして自然数に表せますし、ご存じの通りコンピュータの中ではすべてが二進数で表わされていますので、結局|x|=nなるxは、nビットの0と1で表わされる二進数の元を持つ集合{0,1}^n(※)の元ということにもなります。

※注：{0,1}^nの　^nの部分はべき乗を表わす数字のように右肩に乗るようなものですが、便宜上、以下このように表わしていきます)

このような場合、言語LがTMのプログラムMで決定されるとすると以下のような定理がなり立つという事になります。

「プログラムMで決定される言語LはサイズがO(t(n)log s(n))のサーキットで表わされる」
（※註：テキストでも証明は省略されており、参考文献があります。「I.Wegener, The complexity of Boolean Functions, John Wiley and Teubner,1987 pp.271-277」）

この定理は要するに、クラスP は多項式サイズのサーキットによって計算可能ということになります。当然と言えば当然ですけど、結構これも難しい証明があるようですね。

もう少し考察を進めると、ここまで、多項式サイズのサーキットであっても計算量がクラスPであるためにはユニフォームという条件が必要だということでお話をしていました。言い換えれば、クラスPはユニフォームな多項式サイズのサーキットで表わされる言語全体と言うこともつまりそう定義することも可能ということになります。

さて、ここからはテキストを引用して終わりましょう。一部前回引用した部分も含みます。

「（上のようにクラスPがユニフォームな多項式サイズのサーキットで表わされる言語全体と定義できると言うことは）NC^1とPとの関係において重要である。すなわちNC^1は多項式サイズの論理式、Pは多項式サイズのサーキットということになる。この意味ではNC^1はPの純粋な部分という気分がする。したがってPについての問題はNC^1にあてはめてまず考えるのが良いと思う。特にP=NPの問題のためには、まず

　NC^1≠AC^1

をかんがえ、解決するのが本質に迫る方法の一つだと思う」