回路計算量

回路計算量について

回路計算量（circuit complexity）とは、計算複雑性理論の一部であり、ブール関数をその計算に必要な資源の観点から分類する手法を指します。具体的には、論理回路の大きさや深さをもとにブール関数を評価し、それに基づいて計算量を定義します。

基本概念

論理回路は、入力ビット数が n の場合、有向非巡回グラフとして表現されます。ここでは、各ノードが「ゲート」と呼ばれ、入次数が0のノードがどの入力ビットに対応するかを示します。ゲートはANDゲート、ORゲート、NOTゲートなどであり、これらのうちの一つが出力ゲートとなります。この回路によって、n 個の入力に対する関数が計算されます。回路計算量を評価するために、回路の大きさとは全ゲート数を示し、深さは入力ゲートから出力ゲートまでの最長の経路を表します。

特定のブール関数 f の回路計算量は、f を計算する最も小規模または最も浅い回路の大きさや深さによって定義されます。この分野の研究目的は、ブール関数の中で最小限の大きさや深さを持つものを見つけ出すことです。nビットの入力に対する関数 f の回路計算量を求める方法としては、サイズが小さい関数 f_1, f_2, ... から始め、漸近的に複雑さを求める手法がよく使われます。

複雑性クラス

回路計算量に関連する複雑性クラスとしては、AC0、AC、TC0、NC といった分類があります。これらは、論理回路の性質に基づいて設計されており、各クラスは特定の計算リソースの制約に応じたものとなっています。

一様性と非一様性

論理回路は、計算模型の視点から見れば非一様な例と言えます。入力長が異なる場合、それに合わせて回路も異なるからです。一方で、チューリングマシンなどの一様な計算モデルでは、同じ計算機械が任意の入力長に対応できるため、この点で明確な違いが存在します。つまり、特定の計算問題には、その入力長に応じた複数の論理回路が存在し、各回路は入力ビット数に応じた計算リソースの制限のもとで機能します。

歴史的背景

回路計算量に関する研究は、1999年にVollmerによって書かれた著書によって大きく進展しました。特に、1976年にSavageが発表した著作がこの分野において重要な影響を与えました。

主な研究成果

ブール関数の中でも、入力ビット数が奇数である限り1を返す関数PARITYは、クラス AC0 に含まれないことが示されています。これは、Ajtai（1983年）やFurst、Saxe、Sipser（1984年）が独立して発見した事実です。さらに、Hasted（1987年）はPARITYを計算する回路が指数関数的な大きさになることを証明しました。Smolensky（1987年）は、入力ビット数をカウントして特定の素数で割った余りを出力する回路でも同様の性質が示されることを立証しています。

また、単調関数であるCLIQUが多項式サイズの単調回路で計算できないことがRazborov（1985年）によって最初に発見され、以降AlonとBoppana（1987年）がさらに研究を進めました。

複雑性クラスの階層

回路計算量の複雑性クラスの多くは層次的に定義され、NCiというクラスが任意の整数 i に対して存在します。これらのクラスには、深さがO(log^i(n))に制限されたAND/OR/NOTゲートを用いた多項式サイズの回路が含まれます。これら全体をNCクラスと呼び、無制限のゲートを扱う場合には、ACクラスが定義されます。

このように、回路計算量は計算理論において重要な役割を持っており、新たな知見を追求することで、より深くこの分野を理解する手助けとなります。

もう一度検索