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

おはようございます。いかに失うものもないタコのようなふにゃふにゃのしている私でも、いろいろ悲しいことはあります。しかし、生きているだけで必要にして十分であるはず。ええ、すでに何を言っているか自分でも分りませんが、さて、今回のことをきちんと説明できるのでしょうか。


前回クラスγ/Fを

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

と定義するとき、γ=P、F=Polyの場合すなわちP/Polyが重要であるというお話をしました。今回は、以下の定理を説明します。

【定理】　L∈P/Polyの必要十分条件は
　　

で定義されるブール関数の列fnが多項式サイズのサーキットで計算されることである。

すなわち、P/Polyがノンユニフォーム多項式サイズのサーキットの表わすクラスである

【証明】
(i)L∈P/Polyを仮定する

このときPに属するB（①式での∃B∈γの部分）とPolyに属するh（①式でのh∈Fの部分）で

　　　　L={x｜<x,h(|x|)>∈B}　

を満たすものがあるという事になります。以下n=|x|と表わすこととし、

　　　　m=|<x,h(n)>|

と定義すれば、多項式サイズのサーキットCmで


　　　　<x,h(|x|)>∈B　iff Cmは<x,h(|x|)>に対して1を計算する
　
　　　　　※iffは同値関係をあらわす


を満たすものが存在するという事になります。なぜなら、定義から「<x,y>はO(|x|+|y|)の時間でx,yが計算される」からです。(前回の記事を参照して下さい）

また、Cm以外のリーフがm個のサーキット全体C'nを考えても、mはnで押さえられており、かつ仮定からLはクラスPであり、Pであれば、前々回説明したように　多項式サイズのサーキットによって計算可能となるからです。従って、まず必要条件の証明が終わりました。


(ii)Lが多項式サイズのサーキットCnで決定されると仮定する

このCnをコーティングするようなh(n)があり、|h(n)|はnの多項式p(n)によって押さえられる、すなわち

　　　|h(n)|≦p(n)

であるとします。このことは、すなわち、h∈Polyである事を意味しますね。（前回のPolyの定義を参照して下さい）

一方仮定より、入力xと与えられたCnから出力が1か0かというのは多項式時間により決定できますから、クラスPであることは明らかです。このことをBとすると、

　　 x∈L　iff <x,|h(x)|>∈B

となりますので、L∈P/Polyが導かれ、十分条件が証明されました


単にPをユニフォームな多項式サイズのサーキットであると見なせる観点から、P/PolyをノンユニフォームPと呼ばれるとテキストにはあります。

次回はもう少し補足説明をして、今回のクラスの話を終えたいと思っています。しかし、もう少し説明することもあるかなとも考えていますので、現在少し悩んでいるところです。