回路の複雑さ

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

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

ブール回路で定義される複雑度クラスには、 AC ⁰、AC、TC ⁰、NC ¹、NC、P/poly などがあります。

入力ビットを持つブール回路は、有向非巡回グラフであり、各ノード (このコンテキストでは通常ゲートと呼ばれる) は、入力ビットの 1 つでラベル付けされた入次数0の入力ノード、 AND ゲート、OR ゲート、またはNOT ゲートのいずれかです。これらのゲートの 1 つは出力ゲートとして指定されます。このような回路は、当然、入力の関数を計算します。回路のサイズは、そこに含まれるゲートの数であり、深さは、入力ゲートから出力ゲートまでのパスの最大長です。 ${\displaystyle n}$${\displaystyle n}$${\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}$${\displaystyle 0}$${\displaystyle n}$${\displaystyle C_{n}}$

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

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

ブール回路の族が多項式時間一様であるとは、決定性チューリングマシンMが存在し、 ${\displaystyle \{C_{n}:n\in \mathbb {N} \}}$

• Mは多項式時間で実行される
• 全ての に対して、Mは入力のの記述を出力する。${\displaystyle n\in \mathbb {N} }$${\displaystyle C_{n}}$${\displaystyle 1^{n}}$

ブール回路の族が対数空間一様であるとは、決定性チューリングマシンMが存在し、 ${\displaystyle \{C_{n}:n\in \mathbb {N} \}}$

• Mは対数作業空間で実行される（つまり、Mは対数空間トランスデューサである）
• 全ての に対して、Mは入力のの記述を出力する。${\displaystyle n\in \mathbb {N} }$${\displaystyle C_{n}}$${\displaystyle 1^{n}}$

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

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

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

1999年に、ラズとマッケンジーは、単調なNC階層が無限であることを示した。^[11]

整数除算問題は均一TC ⁰にある。^[12]

回路の下限値は一般的に難しい。既知の結果には以下が含まれる。

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

^{NEXPTIME に非均一な TC 0}回路 があるかどうかは不明です。

回路下限の証明は、非ランダム化と密接に関係している。その証明は、 または が多項式サイズと多項式次数の非均一演算回路（多項式）によって計算できないことを意味する。 ^[16]${\displaystyle {\mathsf {P}}={\mathsf {BPP}}}$${\displaystyle {\mathsf {NEXP}}\not \subseteq {\mathsf {P/poly}}}$

1997年、ラズボロフとルディッチは、明示的なブール関数の多くの既知の回路下限が、それぞれの回路クラスに対して有用ないわゆる自然特性の存在を意味することを示しました。 ^[17]一方、P/polyに対して有用な自然特性は、強力な疑似乱数生成器を破ります。これは、強力な回路下限を証明するための「自然証明」の障壁として解釈されることがよくあります。2016年、カルモシーノ、インパグリアッツォ、カバネッツ、コロコロバは、自然特性を使用して効率的な学習アルゴリズムを構築することもできることを証明しました。^[18]

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

ある言語 が何らかの関数 の時間計算量クラスに属する場合、 は回路計算量 を持ちます。その言語を受け入れるチューリングマシンが忘却型（つまり、入力に関係なく同じメモリセルを読み書きする）である場合、 は回路計算量 を持ちます。^[19]${\displaystyle A}$ ${\displaystyle {\text{時間}}(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))}$

単調ブール回路とは、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-2LCCN  87-10388 。(xii+457 ページ) (注: 当時、このテーマに関する影響力のある教科書で、一般に「ブルーブック」として知られていました。計算複雑性に関する電子コロキウムからダウンロード (PDF) することもできます。)
• Zwick, Uri . 「回路の複雑性に関する Uri Zwick の講義ノート」