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

おはようございます。ではなく、今日はになってしまいました。団体競技だとユニフォームがありますよね。無いと何となく締まらない感じがするのは私だけでしょうか。しかし、学校の制服となるとどうなんでしょうね。そういうふうに、いろいろ悩ましいユニフォームですが、サーキットのクラスにおいてもなかなか悩ましく、いやいや、だからって何もない方が良いって事じゃ無いんですけどね。

今回はノンユニフォームの場合を考えると言うことでした。

まず、現在考えている族{C1,C2,…}で表わされたサーキットや論理式がサイズにおいてが多項式サイズであるという制限を外すとどうなるかというと、インデグリー1であってもチューリングマシンでの計算自体は多項式時間で終わらない可能性のあるものはいくらでも考えられますので、そういうものは計算不可能すなわちクラスPには入らないということになります。

そこで、NC^iやAC^iについて考えるときユニフォーム即ち以下の定義を「サーキットの計算量の様々なクラス　その2」示していますが


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

　f(i)=Ci　

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



この制限を廃したNC^iやAC^iについて考える、という事になります。

これがこれからの流れにおいて考慮に入れておく点ですが、その他いくつかこれまで省略しておいたPSPACEというものを補足したいと思います。

まず、現在TM（以下チューリングマシンをこう表記する）で多項式時間で解けるかどうかがクラスPに入る問題かどうかと言うことでインプットxに対しn=|x|としたときの時間t(n)をもっぱら扱ってきましたが、一方でTMのヘッドの動く距離（あるいはテープの動く距離）が有限であるかどうか問うことも問題となるということを「クラスPとチューリングマシンその2」）においても簡単に触れていました。ここでは、その空間的な量をs(n)と表わすことにし、その量が多項式で表せるものを多項式空間PSPACEとします。

ところで、ヘッドはテープの同じ場所を何度も訪れることができるために、一般に

　P⊆PSPACE

であることは容易に分ります。

ところで、多項式空間では無く、TMのプログラムがO(log n)で必ず停止し受容されると言うようなプログラムのクラスもあります。これはLOGSPACEもしくはLSPACEで表わされ、時には単にLと書かれる場合もあります。

LとPの関係は

　L⊆P

となっているようですが、はっきり証明があって分っているのは

　L≠PSPACE

そして、

　NC^1⊆LSPACE⊆AC^1

などで、分っていないことがかなり多いとテキストには書かれています。