算術回路の複雑度

計算複雑性理論において、算術回路は多項式を計算するための標準モデルです。非公式には、算術回路は変数または数値のいずれかを入力として受け取り、既に計算済みの2つの式を加算または乗算することができます。算術回路は、多項式の計算の複雑さを理解するための形式的な方法を提供します。この研究分野における基本的な質問は、「与えられた多項式を計算する最も効率的な方法は何か」です。${\displaystyle f}$？

算術回路${\displaystyle C}$フィールド全体にわたって${\displaystyle F}$そして変数のセット${\displaystyle x_{1},\ldots ,x_{n}}$これは、次のような有向非巡回グラフです。その中の入次数がゼロのすべてのノードは入力ゲートと呼ばれ、変数によってラベル付けされます。${\displaystyle x_{i}}$またはフィールド要素${\displaystyle F.}$隔門には、${\displaystyle +}$または${\displaystyle \times$ ;} 最初のケースでは和ゲート、2 番目のケースでは積ゲートです。算術式は、すべてのゲートの出次数が 1 である回路です(したがって、基となるグラフは有向木です)。

回路には、サイズと深さという2つの複雑性指標があります。回路のサイズは回路内のゲートの数であり、回路の深さは回路内の最長の有向パスの長さです。例えば、図の回路はサイズが6、深さが2です。

算術回路は、次の自然な方法で多項式を計算します。入力ゲートは、ラベル付けされた多項式を計算します。加算ゲート${\displaystyle v}$子ノードによって計算された多項式の合計を計算します（ゲート）${\displaystyle u}$の子供です${\displaystyle v}$有向エッジの場合${\displaystyle (v,u)}$はグラフに示されています。積ゲートは、その子によって計算された多項式の積を計算します。たとえば、図の回路を考えてみましょう。入力ゲートは（左から右に）${\displaystyle x_{1},x_{2}}$そして${\displaystyle 1,}$合計ゲートは計算します${\displaystyle x_{1}+x_{2}}$そして${\displaystyle x_{2}+1,}$そして、積ゲートは計算します${\displaystyle (x_{1}+x_{2})x_{2}(x_{2}+1).}$

多項式が与えられた${\displaystyle f,}$私たちは、それを計算する最良の方法は何なのか、例えば、計算する回路の最小サイズは何か、と自問するかもしれません。${\displaystyle f.}$この質問への回答は2つの部分から成ります。最初の部分は、${\displaystyle f;}$この部分は通常、複雑さの上限と呼ばれます${\displaystyle f.}$2 番目の部分は、他のどの回路もこれより優れたことはできないことを示しています。この部分は、複雑さの 下限と呼ばれます。${\displaystyle f.}$これら二つの課題は密接に関連しているが、下限を証明する方が通常は難しい。なぜなら、下限を証明するには、すべての回路について同時に議論する必要があるからである。

多項式が定義する関数ではなく、多項式の形式的な計算に興味があることに注意してください。たとえば、次の多項式を考えてみましょう。${\displaystyle x^{2}+x;}$2 つの要素からなる体上では、この多項式はゼロ関数を表しますが、ゼロ多項式ではありません。これは、算術回路の研究とブール回路の研究の違いの 1 つです。ブール複雑性では、関数の何らかの表現 (この場合は多項式による表現) よりも、関数を計算することに主に関心があります。これが、ブール複雑性が算術複雑性よりも難しい理由の 1 つです。算術回路の研究は、私たちがほとんど理解していないブールケースの研究への中間段階の 1 つと考えることもできます^{[ 1 ]}。

計算複雑性理論における最も興味深い未解決問題は、P 対 NP問題です。大まかに言うと、この問題は、与えられた問題が解の存在を示すのと同じくらい簡単に解けるかどうかを判断することです。ヴァリアント^{[ 4 ]}は、その先駆的な研究の中で、この問題の代数的類似であるVP 対 VNP問題を提案しました。

クラス VP は P の代数的類似物であり、多項式のクラスです。 ${\displaystyle f}$固定体上の多項式サイズの回路を持つ多項式次数${\displaystyle K.}$VNPクラスはNPの類似物である。VNPは多項式のクラスと考えることができる。${\displaystyle f}$多項式の次数によって、与えられた単項式でその係数を決定できる。${\displaystyle f}$効率的に、多項式サイズの回路で動作する。

複雑性理論における基本的な概念の 1 つは、完全性の概念です。多項式のクラス (VP や VNP など) が与えられた場合、完全多項式は${\displaystyle f}$このクラスでは、次の 2 つの特性を持つ多項式です。(1) クラスの一部であること、(2) 他の任意の多項式${\displaystyle g}$クラスでは、${\displaystyle f,}$つまり、${\displaystyle f}$小さな回路があれば、${\displaystyle g.}$Valiantは、クラスVNPにおいてパーマネントが完全であることを示した。したがって、VPがVNPと等しくないことを示すには、パーマネントが多項式サイズの回路を持たないことを示す必要がある。これは未解決の難問として残っている。

多項式の計算に関する理解のベンチマークの 1 つは、Valiant、Skyum、Berkowitz、および Rackoff の研究です。^{[ 5 ]}彼らは、多項式が${\displaystyle f}$学位${\displaystyle r}$サイズの回路を持つ${\displaystyle s,}$それから${\displaystyle f}$また、サイズの多項式の回路も持っています。${\displaystyle r}$そして${\displaystyle s}$深さ${\displaystyle O(\log(r)\log(s)).}$例えば、次数が の任意の多項式${\displaystyle n}$多項式サイズの回路を持つもの、深さがおよそ多項式サイズの回路も持つ${\displaystyle \log ^{2}(n).}$この結果は、ベルコウィッツの回路を、多項式サイズの回路（例えば行列式）を持つ任意の次数多項式に一般化するものである。ブール論理におけるこの結果の類似は偽であると考えられている。

この結果の帰結の一つは、比較的小さな式、準多項式サイズの式による回路のシミュレーションです。多項式が${\displaystyle f}$学位${\displaystyle r}$サイズの回路を持つ${\displaystyle s,}$すると、サイズの公式が${\displaystyle s^{O(\log(r))}.}$このシミュレーションはValiantらによる深度低減よりも簡単で、以前にHyafilによって示されました。^{[ 6 ]}

• 多項式評価の複雑さについて、より一般的で形式ばらない議論を行うための多項式評価。

• Bürgisser, Peter (2000).代数的複雑性理論における完全性と還元. 数学におけるアルゴリズムと計算. 第 7 巻. ベルリン: Springer-Verlag . ISBN 978-3-540-66752-0. Zbl 0948.68082 . 
• ピーター・ビュルギッサー;クラウセン、マイケル。Shokrollahi、M. アミン(1997)。代数的複雑性理論。 Grundlehren der Mathematischen Wissenschaften。 Vol.  315. トーマス・リックタイグの協力による。ベルリン: Springer-Verlag。ISBN 978-3-540-60582-9. Zbl 1087.68568 . 
• von zur Gathen, Joachim (1988). "代数的複雑性理論". Annual Review of Computer Science . 3 : 317–347 . doi : 10.1146/annurev.cs.03.060188.001533 .