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

おはようございます、ではなくすでに、こんにちはですね。いや、がんばっている分、眠くなる今回の記事。報われない思いがするのは私だけでしょうか。などと言いつつ、途中疲れて寝てしまったのも私。まったく反省しきりでございます。


さて今回から、ノンユニフォームの多項式サイズのサーキットを表わすクラスについて、以下数回にわたって考えていくことになります。

前回同様、注意点としてx^iという式の^はべき乗を表わす二項演算子とします。

今回は必要な定義についてです。いろいろ記号が出てきます。できるだけ解説を入れて説明したいと思いますが、「チューリングマシンの数理モデル」や「クラスPとチューリングマシンその１」などの記事もご参考頂ければ幸いです。


【関数集合Fの定義】
まず、Fをh:N→Σ*なる関数hの集合とします。ここで、Nは自然数全体の集合、Σ*は入力記号の全体の集合。従ってここではすべて自然数があればそれを入力全体の集合にするようなそのような関数をh、その集合をFとすると言い換えることができます。


【関数集合Polyの定義】
次に、Polyを定義して、|h(n)|がn（入力xとしたときの|x|）の多項式で押さえられているすべてのh:N→Σ*の関数の集合とします。


【関数集合γおよびγ/Fの定義】
γをL⊆{0,1}*なる言語Lのクラス、即ち、言語Lはすべての2進数全体の部分集合で、Lの中の集合（クラス）をγとしたときに

　　　　< , >:({0,1}*)^2→{0,1}*

が1対１の写像を表わす関数、言い換えれば、({0,1}*)^2を{0,1}*にへのコーディングであり

　　　　|<x,y>|=O(|x|+|y|)

を満たすものであるとする。ただし<x,y>はO(|x|+|y|)の時間でx,yが計算されるものとする。このような<,>の例はいくらでもありますね。

このとき、Fの助けを借りて、γから計算できるクラスγ/Fを次の式で定義するものとします。

　　　γ/F={L⊆{0,1}*|∃B∈γ,h∈F,L=｛x｜<x,h(|x|)>∈B}

これは、非常にややこしいのですが慣れて頂くほかなく、まず、L=｛x｜<x,h(|x|)>∈B}によってBが規定され、そのうちの∃Bを元とするという事で
が規定されています。なんだこりゃですね。

こうしてみると、<x,h(|x|)>が与えられればxは簡単に計算できます。すなわち、この場合h(|x|)が助けを与えているわけですが、そういう余分な情報を<x,h(|x|)>は持っていると見なせるということになります。

さて、このような場合

　γ＝P, F=Poly

のP/Polyが重要になってくるということで、次回からはこの解説になります。