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

おはようございます。一粒で何度でもおいしいこの冒頭のつかみの部分。実はこの部分が一番時間と労力を使っているのでは無いかと思われるというのは内緒です。いや、しかし、よく考えればそれこそP=NP問題。テキストに書かれている部分は分っている事実ですので計算量はクラスP ですからね。だから難しくないか、といえばそうでもないところが、この世の深淵に触れる一事実というべきなのでしょうか。


さて、前回は、ノンユニフォームを考える場合の制限とPSPACE、LSPACE（この記事ではLとも表記される）について少し触れました。空間についての計算量の考察は、

　L⊆P

　L≠PSPACE

　NC^1⊆LSPACE⊆AC^1

が前回挙げられた証明済みの関係ですが、ユニフォームの制限がある場合、一般に、

　NC^0⊆AC^0⊆NC^1⊆AC^1⊆NC^2⊆AC^2⊆………⊆NC=AC⊆P

という事が成り立ちますから、LSPACEをLと表わすと

　　NC^0⊆AC^0⊆NC^1⊆L⊆AC^1⊆NC^2⊆AC^2⊆………⊆NC=AC⊆P

という事は容易に分かると思います。しかし、この包含関係のイコールの部分が成立するかどうかについては、一般には成立しないと思われているようですが、この予想で証明があるのは、

　AC^0≠NC^1

だけという大変難しい問題のようです。

竹内先生におかれましては、このあと、P=NP問題については、


「
　NC^1≠AC^1

を考え解決するのが本質に迫る方法の一つと思う」(テキストp.47)


と書かれています。これについては追々説明していくということで、まず、ノンユニフォームでの場合のNC^1についてもう少し分っている事実などを述べていきたいと思います。

NC^1について、多項式このインデグリーを2に直すのに必要な計算量はO(log n)になることは自明だと思います。次に多項式個のアウトデグリーを1個のアウトデグリーに変換するには多項式時間で済むという事になります。言い換えると、NC^1は多項式サイズの論理式に変換することができるでしょう。

ところで、証明は省略しますが、Spiaの定理というものがスレッシュホールド関数を扱う場合分っている事実として証明されていますので、これを使うと、NC^1は多項式サイズで深さがO(log n)の論理式で表わされるという事が分かるということになるようです。

「このようなNC^1の定式化はNC^1の内容を良く表わす上で重要である」(テキスト p46)

と竹内先生は書かれていますので、ご紹介しておきます。