回路の複雑さ

理論計算機科学において、回路複雑性は計算複雑性理論の一分野であり、ブール関数はそれを計算するブール回路のサイズまたは深さに基づいて分類される。関連する概念として、均一な回路群によって決定される再帰言語の回路複雑性がある。${\displaystyle C_{1},C_{2},\ldots }$（以下を参照してください）。

明示的なブール関数を計算するブール回路のサイズの下限を証明することは、複雑性クラスを分離するための一般的なアプローチです。たとえば、有名な回路クラスP/polyは、多項式サイズの回路で計算可能なブール関数で構成されています。$\displaystyle {\mathsf {NP}}\not \subseteq {\mathsf {P/poly}}}$PとNPを分離する（下記参照）。

ブール回路の観点から定義される複雑度クラスには、 AC ⁰、AC、TC ⁰、NC ¹、NC、およびP/polyが含まれます。

ブール回路${\displaystyle n}$input bitsは、各ノード (この文脈では通常ゲートと呼ばれる) が、次数0の入力ノードで、${\displaystyle n}$入力ビット、ANDゲート、ORゲート、またはNOTゲート。これらのゲートのうちの1つが出力ゲートとして指定されます。このような回路は、入力ビットの関数を自然に計算します。${\displaystyle n}$入力。回路のサイズは、回路に含まれるゲートの数であり、深さは、入力ゲートから出力ゲートまでの経路の最大長です。

回路複雑性には大きく分けて2つの概念がある。^{[ 1 ]}ブール関数の回路サイズ複雑性${\displaystyle f}$は、あらゆる回路コンピューティングの最小サイズです。${\displaystyle f}$ブール関数の回路深度複雑度${\displaystyle f}$は、あらゆる回路コンピューティングの最小深度です。${\displaystyle f}$。

これらの概念は、異なるビット長の文字列を含むあらゆる形式言語、特に無限言語の回路複雑性を考慮する際に一般化される。しかし、ブール回路は固定数の入力ビットしか許容しない。したがって、単一のブール回路ではそのような言語を判定することはできない。この可能性を考慮するために、回路のファミリーを考慮する。${\displaystyle C_{1},C_{2},\ldots }$それぞれ${\displaystyle C_{n}}$サイズの入力を受け付けます${\displaystyle n}$各回路ファミリーは、回路ごとに自然に言語を生成します。${\displaystyle C_{n}}$出力${\displaystyle 1}$長さ${\displaystyle n}$string はファミリーの一員であり、${\displaystyle 0}$それ以外の場合。入力のサイズが任意のサイズである場合に、回路のファミリーが最小サイズであると言います。${\displaystyle n}$より小さいサイズの回路で${\displaystyle C_{n}}$（それぞれ深さ最小のファミリーの場合）。したがって、回路複雑性は非再帰言語に対しても意味を持ちます。均一ファミリーの概念により、回路複雑性のバリアントを再帰言語のアルゴリズムベースの複雑性尺度と関連付けることができます。ただし、非均一バリアントは、与えられた言語を決定するために、任意の回路ファミリーがどの程度複雑でなければならないかの下限を見つけるのに役立ちます。

したがって、形式言語の回路サイズ複雑度${\displaystyle A}$関数として定義される${\displaystyle t:\mathbb {N} \to \mathbb {N} }$入力のビット長に関連する、${\displaystyle n}$最小回路の回路サイズ複雑度まで${\displaystyle C_{n}}$その長さの入力が${\displaystyle A}$回路深度複雑度も同様に定義される。

ブール回路は、入力の長さが異なると異なる回路で処理されるという意味で、いわゆる非均一計算モデルの代表的な例の一つである。これは、チューリングマシンなどの均一モデルでは、すべての入力長に対して同じ計算装置が使用されるのとは対照的である。したがって、個々の計算問題は、特定のブール回路群に関連付けられる。${\displaystyle C_{1},C_{2},\dots }$それぞれ${\displaystyle C_{n}}$は、 nビットの入力を処理する回路です。これらの回路群にはしばしば均一性条件が課され、入力nに対して個々の回路の記述を生成する、リソースに制約のあるチューリングマシンの存在が要求されます。${\displaystyle C_{n}}$このチューリングマシンの実行時間がnに関する多項式である場合、回路ファミリーは P-一様であると言われます。より厳密なDLOGTIME-一様性の要件は、AC ⁰や TC ⁰のような浅い深さの回路クラスの研究において特に重要です。リソースの境界が指定されていない場合、言語が再帰的（つまり、チューリングマシンで決定可能）であるのは、その言語が一様族のブール回路によって決定される場合に限ります。

回路の複雑性は、1949年にシャノン^{[ 2 ]}がn個の変数に対するほとんどすべてのブール関数はΘ(2n/n)サイズの回路を必要とすることを証明したこと^に遡ります。この事実にもかかわらず、複雑性理論家はこれまで、明示的な関数に対する超線形下限を証明できていません。

超多項式の下限は、使用する回路のファミリーに特定の制約がある場合にのみ証明されています。超多項式の回路下限が示された最初の関数は、入力ビットの合計を法 2 で計算するパリティ関数です。パリティがAC ⁰に含まれないという事実は、1983 年にAjtai ^{[ 3 ] [ 4 ]}と1984 年にFurst、Saxe、Sipser ^{[ 5 ]}によって独立に初めて確立されました。1987 年にHåstad ^{[ 6 ]}によるその後の改良により、パリティ関数を計算する定数深さの回路のファミリーは指数関数的なサイズを必要とすることが確立されました。Razborov ^{[ 7 ]}の結果を拡張して、1987 年に Smolensky [ ^{8 ]は}、回路が奇素数pを法とする入力ビットの合計を計算するゲートで拡張されている場合でもこれが真であることを証明しました。

k-クリーク問題とは、 n個の頂点を持つ与えられたグラフにサイズkのクリークが存在するかどうかを判定する問題である。定数nとkの任意の選択に対して、グラフはバイナリでエンコードできる。${\displaystyle {n \choose 2}}$各可能なエッジが存在するかどうかを示すビット。次に、k-クリーク問題は関数として定式化される。${\displaystyle f_{k}:\{0,1\}^{n \choose 2}\to \{0,1\}}$そのため${\displaystyle f_{k}}$文字列によってエンコードされたグラフにサイズkのクリークが含まれる場合に限り、出力は 1 になります。この関数の族は単調であり、回路の族によって計算できますが、多項式サイズの単調回路の族 (つまり、AND ゲートと OR ゲートはありますが、否定がない回路) では計算できないことが示されています。1985 年の Razborov による元の結果^{[ 7 ]}は、後に 1987 年にAlonと Boppanaによって指数サイズの下限に改善されました。 ^{[ 9 ]} 2008 年にRossman ^{[ 10 ]}は、AND、OR、NOT ゲートを持つ定数深さの回路にはサイズが必要であることを示しました。${\displaystyle \オメガ (n^{k/4})}$平均的な場合でもk-クリーク問題を解決する。さらに、サイズの回路が存在する。${\displaystyle n^{k/4+O(1)}}$計算する${\displaystyle f_{k}}$。

1999年、RazとMcKenzieは後に、単調NC階層が無限であることを示した。^{[ 11 ]}

整数除算の問題は一様TC ⁰にある。^{[ 12 ]}

回路の下限を求めるのは一般的に難しい。既知の結果には以下のようなものがある。

• パリティは非一様AC ⁰には存在しないことが、1983 年に Ajtai ^{[ 3 ] [ 4 ]}および 1984 年に Furst、Saxe、Sipser によって証明されている^{[ 5 ]。}
• 一様TC ⁰はPPに厳密に含まれており、 Allenderによって証明されている。^{[ 13 ]}
• クラスO ^P ₂、^{[ 14 ]} PP ^{[ nb 1 ]}およびMA /1 ^{[ 15 ]} (1 ビットのアドバイス付き MA) は、任意の定数 k に対してSIZE ( n ^k ) には含まれません。
• 非一様クラスACC ⁰には多数決関数が含まれていないと疑われているが、ウィリアムズがそれを証明したのは 2010 年になってからだった。${\displaystyle {\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}}$[ ^{16 ]​}

NEXPTIMEに非均一なTC ⁰回路が存在するかどうかは不明である。

回路下限の証明は、脱ランダム化と密接に関連している。${\displaystyle {\mathsf {P}}={\mathsf {BPP}}}$どちらかが${\displaystyle {\mathsf {NEXP}}\not \subseteq {\mathsf {P/poly}}}$または、行列のパーマネントは、多項式サイズと多項式次数を持つ非一様算術回路（多項式）では計算できない。^{[ 17 ]}

1997年、RazborovとRudichは、明示的なブール関数の既知の回路下限の多くが、それぞれの回路クラスに対して有用ないわゆる自然特性の存在を意味することを示した。 ^{[ 18 ]}一方、P/polyに対して有用な自然特性は、強力な擬似乱数生成器を破壊する。これは、強力な回路下限を証明するための「自然証明」の障壁として解釈されることが多い。2016年、Carmosino、Impagliazzo、Kabanets、Kolokolovaは、自然特性は効率的な学習アルゴリズムの構築にも使用できることを証明した。^{[ 19 ]}

多くの回路複雑度クラスは、クラス階層によって定義されます。各非負整数iに対して、深さ の多項式サイズの回路からなるクラスNC ^{iが存在します。}${\displaystyle O(\log ^{i}(n))}$ファンインに制限のあるAND、OR、NOTゲートを使用します。これらのクラスすべての和集合NCは研究対象です。ファンインに制限のないゲートを考慮すると、クラスAC ⁱとAC（NCに等しい）を構築できます。異なるゲートセットを許可することで、同じサイズと深さの制限を持つ他の多くの回路複雑性クラスを構築できます。

ある言語の場合、${\displaystyle A}$時間計算量クラスに属する${\displaystyle {\text{TIME}}(t(n))}$ある関数に対して${\displaystyle t:\mathbb {N} \to \mathbb {N} }$、 それから${\displaystyle A}$回路の複雑さがある${\displaystyle {\mathcal {O}}(t(n)\log t(n))}$言語を受け入れるチューリングマシンが無自覚である場合（つまり、入力に関係なく同じメモリセルを読み書きする場合）、${\displaystyle A}$回路の複雑さがある${\displaystyle {\mathcal {O}}(t(n))}$[ ^{20 ]​}

単調ブール回路とは、ANDゲートとORゲートのみを持ち、NOTゲートを持たない回路のことです。単調回路は、単調ブール関数のみを計算できます。単調ブール関数とは、関数です。${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$すべての${\displaystyle x,y\in \{0,1\}^{n}}$、${\displaystyle x\leq y\implies f(x)\leq f(y)}$、 どこ${\displaystyle x\leq y}$つまり${\displaystyle x_{i}\leq y_{i}}$すべての人々のために${\displaystyle i\in \{1,\ldots ,n\}}$。

• 回路の最小化

• Vollmer, Heribert [ドイツ語] (1999).回路複雑性入門：統一的アプローチ. 理論計算機科学テキストシリーズ. EATCSシリーズ. Springer Verlag . ISBN 978-3-540-64310-4。
• ウェゲナー、インゴ(1987) [1986 年 11 月]。ブール関数の複雑さ。コンピューターサイエンスのワイリー・トイブナーシリーズ。フランクフルト・アム・マイン/ビーレフェルト、ドイツ：John Wiley & Sons Ltd.、およびBG Teubner Verlag、シュトゥットガルト。ISBN 3-519-02107-2。LCCN 87-10388。 （xii+457ページ）（注：当時、この分野で影響力のある教科書であり、一般に「ブルーブック」として知られていた。計算複雑性に関する電子コロキウムのウェブサイトからPDF版をダウンロードすることも可能。）
• ズウィック、ウリ。「ウリ・ズウィックによる回路複雑性に関する講義ノート」。