ブール回路

計算複雑性理論と回路複雑性において、ブール回路は組み合わせデジタル論理回路の数学的モデルです。形式言語はブール回路の族によって決定することができ、各可能な入力長ごとに 1 つの回路があります。

ブール回路は、含まれる論理ゲートに基づいて定義されます。たとえば、回路にはバイナリ ANDゲートとOR ゲート、および単項 NOT ゲートが含まれる場合もあれば、バイナリNAND ゲートだけで完全に記述される場合もあります。各ゲートは、固定数のビットを入力として受け取り、1 ビットを出力するブール関数に対応します。

ブール回路は、マルチプレクサ、加算器、算術論理ユニットなど、コンピュータ エンジニアリングで使用される多くのデジタル コンポーネントのモデルを提供しますが、シーケンシャル ロジックは除外されます。ブール回路は、メタ安定性、ファンアウト、グリッチ、消費電力、伝播遅延の変動性など、実際のデジタル ロジック回路の設計に関連する多くの側面を省略した抽象化です。

ブール回路の正式な定義を与えるにあたり、フォルマーは、回路モデルで許容されるゲートに対応するブール関数の集合Bとして基底を定義することから始めます。基底B上のn入力とm出力を持つブール回路は、有限有向非巡回グラフとして定義されます。各頂点は基底関数または入力の 1 つに対応し、出力としてラベル付けされたちょうどm 個のノードの集合があります。 ^{[1] : 8}また、同じブール関数の異なる引数を区別するために、エッジには何らかの順序付けが必要です。^{[1] : 9}

特殊なケースとして、命題式またはブール式は、 1 つの出力ノードを持ち、他のすべてのノードのファンアウトが1 であるブール回路です。したがって、ブール回路は、共有サブ式と複数の出力を可能にする一般化と見なすことができます。

ブール回路の共通の基礎は、機能的に完全な集合 { AND、OR、NOT } です。つまり、そこから他のすべてのブール関数を構築できます。

特定の回路は、固定サイズの入力に対してのみ作用する。しかし、形式言語（決定問題の文字列ベースの表現）には異なる長さの文字列が含まれるため、言語を単一の回路で完全に表現することはできない（言語が単一のチューリングマシンで完全に記述されるチューリングマシンモデルとは対照的である）。言語は、代わりに回路ファミリによって表現される。回路ファミリは、回路の無限リストであり、 は入力変数である。回路ファミリは、すべての文字列 に対して、 が言語に含まれる場合、かつ が（ の長さ）である場合に限り、言語を決定すると言われる。言い換えれば、言語とは、長さに対応する回路に適用されたときに が 1 に評価される文字列の集合である。^{[2] : 354}${\displaystyle (C_{0},C_{1},C_{2},...)}$${\displaystyle C_{n}}$${\displaystyle n}$${\displaystyle L}$${\displaystyle w}$${\displaystyle w}$${\displaystyle L}$${\displaystyle C_{n}(w)=1}$${\displaystyle n}$${\displaystyle w}$

@クラビス

ブール回路では、回路の深さ、回路のサイズ、AND ゲートと OR ゲートの交替回数など、 いくつかの重要な複雑さの尺度を定義できます。たとえば、ブール回路のサイズの複雑さは、回路内のゲートの数です。

回路規模の複雑さと時間の複雑さの間には自然な関係があります。^{[2] : 355}直感的には、時間の複雑さが小さい言語（つまり、チューリングマシン上での連続的な操作が比較的少ない言語）は、回路の複雑さも小さいです（つまり、ブール演算が比較的少ない言語）。正式には、言語が（ここでは関数）にある場合、回路の複雑さは であることが示されます。 ${\displaystyle {\mathsf {時間}}(t(n))}$${\displaystyle t}$${\displaystyle t:\mathbb {N} \to \mathbb {N} }$${\displaystyle O(t^{2}(n))}$

いくつかの重要な複雑性クラスがブール回路によって定義されています。これらの最も一般的なクラスはP/polyで、多項式サイズの回路族によって決定可能な言語の集合です。これは、 の言語がP P/polyという回路複雑性を持つという事実から直接導かれます。言い換えれば、決定性チューリングマシンによって多項式時間で計算できる問題は、多項式サイズの回路族でも計算できます。さらに、P/poly に含まれる決定不可能な問題があるため、包含が適切 (つまり P P/poly) であることも当てはまります。 P/poly には、複雑性クラス間の関係の研究に非常に役立ついくつかの特性があることがわかりました。特に、P と NPに関連する問題を調査するのに役立ちます。たとえば、 NP に含まれていて P/poly に含まれない言語がある場合、 P NP です。^{[3] : 286} P/poly は、多項式階層の特性の調査にも役立ちます。たとえば、NP ⊆ P/poly の場合、PH は に縮小されます。P/poly と他の複雑性クラスの関係の完全な説明は、「P/poly の重要性」で参照できます。P/poly には、多項式制限アドバイス関数を備えた多項式時間チューリングマシンによって認識される言語のクラスとして同等に定義できるという興味深い機能もあります。 ${\displaystyle {\mathsf {時間}}(t(n))}$${\displaystyle O(t^{2}(n))}$${\displaystyle \subseteq }$${\displaystyle \subsetneq }$${\displaystyle \neq}$${\displaystyle \Sigma _{2}^{\mathsf {P}}}$

P/poly の 2 つのサブクラスは、 NCとACであり、それ自体が興味深い特性を持っています。これらのクラスは、回路サイズだけでなく、深さの観点からも定義されます。回路の深さは、入力ノードから出力ノードへの最長有向パスの長さです。クラス NC は、多項式サイズだけでなく多対数深さにも制限される回路ファミリによって解決できる言語の集合です。クラス AC は NC と同様に定義されますが、ゲートには無制限のファンインが許可されます (つまり、AND ゲートと OR ゲートは 2 ビット以上に適用できます)。NC は、効率的な並列アルゴリズムを持つ言語のクラスを表すことが判明しているため、重要なクラスです。

回路値問題（与えられた入力文字列に対して与えられたブール回路の出力を計算する問題）はP完全 決定問題である。^{[3] ：119}したがって、この問題は、問題を解決する効率的で高度に並列化されたアルゴリズムが存在しない可能性が高いという意味で「本質的に順次的」であると考えられている。

論理回路は、AND、OR、NOT などの単純な論理演算 (およびそれらの組み合わせ、たとえば非連続フリップフロップや回路ネットワーク) の物理的表現であり、ブール代数と呼ばれる数学的構造を形成します。任意の決定論的アルゴリズムを実行できるという意味で、論理回路は完全です。しかし、それだけではありません。物理世界ではランダム性も存在します。これは量子力学の理論で説明される量子化効果によって支配される小さなシステムで顕著です。論理回路はランダム性を生成することはできず、その意味では不完全な論理セットを形成します。その解決策は、確率的チューリングマシンなどの論理ネットワークまたはコンピューターにアドホックなランダムビットジェネレーターを追加することです。最近の研究^[4]では、ランダムフリップフロップと呼ばれる本質的にランダムな論理回路の理論的概念が導入され、これによりセットが完成します。これはランダム性を都合よくパックし、決定論的ブール論理回路と相互運用可能です。しかし、ブール代数と同等の代数構造や、拡張セットの回路構築および縮小の関連する方法はまだ知られていません。

• 回路の充足可能性
• 論理ゲート
• ブール論理
• スイッチング補題