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

おはようございます。10月ももうすぐ終わり。そうしている間にあっという間に一年も終わりそうですね。落ち葉の季節も近づきましたが、こちらも大詰め。しかしもう少しでゴールが見えてきそうで見えてこない。ちょうど十月終わりといった状況であります。


今回、「サーキットの計算量の様々なクラス」と題して代表的なクラスの計算量の考え方についてその概要を説明してきました。これがどれほどの意味を持つのか難しく、クラスAとBにおいてのクラスの分類A≠Bという、あまり関係しないのではというのが竹内外史先生のご意見のようです。そういうこともあって、ここまである程度駆け足で見てきました。

これからの進め方ですが、計算量のクラスのお話しは今回でいったん終わり、次回からはモノトーンサーキットでの問題について説明したいと思います。こちらは、分っていることが多く、また、実際の電子回路などの設計にも応用できそうな手法が多く見受けられると言うこと、などがその理由です。

では本題に入ります。

前回クラスγ/Fを

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

と定義するとき、γ=P、F=Polyの場合すなわちP/Polyが重要であり、定理としてP/Polyがノンユニフォーム多項式サイズのサーキットの表わすクラスであること、などをお話をしました。今回、サーキットの計算量の様々なクラスのお話しの最後として、補足説明的なお話しをいくつかさせて頂こうと思います。

やはり前回の最後に、

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

と述べましたが、これに関連して、P=NP問題を解く際、NP⊆Pを解くという方法の他に、

　　　NP⊆P/Poly　

という事の検討興味ある問題だとあります。ここで、P/PolyにはクラスPに入らないものはいくらでもあるためP/PolyがクラスNPに含まれないということは明らかであるために、NP=P/Polyと言わないともあります。たとえば、P/Polyのサーキットのサイズが多項式サイズであっても、結果を自己言及できないために真偽の判断をクラスNPでは判断できない、場合があると考えれば良いのではないでしょうか。

このことに関して、テキストもあまり詳しく触れておらず、ここまで説明を省略してきたTMを拡張したOTMやNOTMを含んだ階層構造、これをポリミナル・ハイアラーキー（PH）と呼びますがこれにも関係してくるという事などが簡単に触れられています。

このあたりの議論に関しては以下の論文などを参照すると良いようです。

「R.M.Karp and R.Lipton, Turing machines that take advice, Enseign.Math,28(1982),191-209.」

これに関連していくつかの数学基礎論的・計算機理論的「言語」も紹介されていますが、今回は省略します。最後にテキストのp.55からのこの節に関する最後の部分を引用して終わりたいと思います。

「　不思議なことに、以下の重大問題、いろいろなクラスA,BについてA≠Bを証明したいという議論の中で、このユニフォームの概念が用いられることはほとんどない。
　まだ学問が未発達で、それが関係する段階に到っていないのか、それとも本質的にクラスの分類A≠Bという問題には、ユニフォームという概念が関係しないのか？すなわち今まで考えられているクラスには、その分離の問題はユニフォームという性質とは独立の問題なのかは分らない。
　しかし著者は後者の方の意見に傾いている。」