ブール回路

ブール回路の例。∧ のノードは ANDゲート、∨ のノードは ORゲート、¬ のノードは NOTゲートを表す。

計算複雑性理論と回路計算量において、ブール回路（ブールかいろ、テンプレート:Lang-en-short）とは、組合せデジタル論理回路を表す数学的モデルである。ブール回路の族が形式言語を判定することが可能であり、各回路は各入力長にひとつずつ対応する。

ブール回路は、それが含む論理ゲートによって定義される。たとえば、ある回路は二項の AND、ORと単項の NOTを含むこともあれば、二項の NANDゲートのみで完全に記述されることもある。各ゲートは固定数のビットを入力として単一のビットを出力する何らかのブール関数に対応する。

ブール回路は計算機工学で用いられる多くのデジタル部品——マルチプレクサ、加算器、演算装置など——のモデルを提供するが、順序回路は除外する。ブール回路は現実のデジタル論理回路の設計に関連する多くの側面、たとえばテンプレート:仮リンク、ファンアウト、ハザード、テンプレート:仮リンク、伝搬遅延のばらつきなどを省略した抽象化である。

形式的定義

ブール回路の形式的定義において、テンプレート:仮リンクはまず、回路モデルで許容されるゲートに対応するブール関数の集合 B を「基底」として定義することから始める。基底 B 上の、n 個の入力と m 個の出力を持つブール回路は、有限有向非巡回グラフとして定義される。各頂点は基底関数または入力の1つに対応し、出力として標識される正確に m 個のノードの集合が存在するテンプレート:Rp。同一のブール関数への異なる引数を区別するため、辺にも何らかの順序が必要であるテンプレート:Rp。

特殊な場合として、命題論理式あるいはブール式は、出力ノードがひとつであり、それ以外のすべてのノードのfan-outが 1 であるようなブール回路である。したがって、ブール回路は部分式の共有と複数の出力を許す一般化とみなすことができる。

ブール回路の共通の基底は集合 {AND, OR, NOT} であり、これは関数完全、すなわち他のすべてのブール関数がここから構成できる。

計算複雑性

背景

個々の回路は固定サイズの入力に対してのみ作用する。しかし、形式言語（決定問題の文字列ベースの表現）は異なる長さの文字列を含むため、単一の回路では言語を完全には捉えられない（言語が単一のチューリングマシンで完全に記述されるチューリングマシン・モデルとは対照的である）。代わりに、言語は「回路族」で表される。回路族は無限個の回路のリスト $(C_0,C_1,C_2,\mathrm{...})$ であり、$C_n$ は $n$ 個の入力変数を持つ。ある回路族が言語 $L$ を判定するとは、任意の文字列 $w$ について、$w$ が言語 $L$ に属することと $C_n(w)=1$（ここで $n$ は $w$ の長さ）が同値となることをいう。言い換えれば、言語とは、それぞれの長さに対応する回路に適用したとき 1 と評価される文字列の集合であるテンプレート:Rp。

複雑性の尺度

テンプレート:See also ブール回路に対しては、回路の深さ、回路のサイズ、AND ゲートと OR ゲートの間の交替の回数など、いくつかの重要な複雑性の尺度を定義できる。たとえば、ブール回路のサイズ複雑性は、回路内のゲートの個数である。

回路サイズ複雑性と時間計算量との間には自然な関係があるテンプレート:Rp。直観的に言えば、時間計算量が小さい言語（すなわち、チューリングマシン上で比較的少数の逐次操作しか必要としない言語）は、回路計算量もまた小さい（すなわち、比較的少数のブール演算しか必要としない）。厳密には、ある言語が $𝖳𝖨𝖬𝖤(t(n))$（$t$ は関数 $t:\mathbb{N}\to \mathbb{N}$）に属するならば、それは回路サイズ複雑性 $O(t^2(n))$ を持つことが示せる。

複雑性クラス

テンプレート:Main ブール回路の観点から定義される重要な複雑性クラスがいくつか存在する。最も一般的なのは テンプレート:仮リンク——多項式サイズの回路族で判定可能な言語の集合——である。$𝖳𝖨𝖬𝖤(t(n))$ に属する言語が回路計算量 $O(t^2(n))$ を持つことから、直ちに P$\subseteq$P/poly が従う。言い換えれば、決定性チューリングマシンで多項式時間内に計算できる任意の問題は、多項式サイズの回路族でも計算できる。さらに包含は真である（すなわち P$⊊$P/poly）。なぜなら P/poly には決定不能な問題も含まれるからである。P/poly は複雑性クラス間の関係の研究において非常に有用な多くの性質を持つ。特に、P対NPに関連する問題の考察に有用である。たとえば、NP 内の言語で P/poly に属さないものがあれば、P$\ne$NP となるテンプレート:Rp。P/poly は多項式階層の性質の研究にも役立つ。たとえば、NP ⊆ P/poly ならば、PH は ${\mathrm{\Sigma }}_2^{𝖯}$ に崩壊する。P/poly と他の複雑性クラスとの関係の完全な記述は英語版「Importance of P/poly」に見ることができる。P/poly は、多項式時間チューリングマシンと多項式的に有界なテンプレート:仮リンクによって認識される言語のクラスとして等価に定義できるという興味深い特徴も持つ。

P/poly の2つの部分クラスで、それ自体興味深い性質を持つものが NC と テンプレート:仮リンク である。これらのクラスは回路サイズだけでなく「深さ」の観点からも定義される。回路の深さとは、入力ノードから出力ノードまでの最長有向路の長さである。クラス NC は、多項式サイズであるだけでなくテンプレート:仮リンク深さでもある回路族で解ける言語の集合である。クラス AC は NC と同様に定義されるが、ゲートは無限のファンインを持つことが許される（すなわち AND と OR のゲートは2ビット以上に適用できる）。NC は重要なクラスであり、効率的な並列アルゴリズムを持つ言語のクラスを表すことがわかっている。

回路評価

テンプレート:仮リンク——与えられたブール回路を与えられた入力バイナリ文字列に対して計算した出力を求める問題——は、テンプレート:仮リンクの決定問題であるテンプレート:Rp。したがって、この問題を解く効率的で高度な並列アルゴリズムはおそらく存在しないという意味で、「本質的に逐次的」であると考えられている。

完全性

論理回路は、AND、OR、NOT という単純な論理演算の物理的表現（および非順序性フリップフロップや回路網などその組合せ）であり、ブール代数として知られる数学的構造をなす。それらは任意の決定的アルゴリズムを実行できるという意味で完全である。しかし、それがすべてではない。物理世界においては、量子力学で記述される、量子化効果に支配される小規模系で顕著な、ランダム性にも遭遇する。論理回路はランダム性を生成できず、その意味では不完全な論理集合を形成する。この対処法として、確率的チューリング機械のように、論理網や計算機にアドホックなランダムビット生成器を追加する方法がある。近年の研究は、この集合を完全化する「ランダム・フリップフロップ」と呼ばれる、本質的にランダムな論理回路の理論的概念を導入した。それは便利にランダム性をパッケージ化し、決定的なブール論理回路と相互運用可能である。しかし、この拡張された集合に対する、ブール代数と等価な代数構造および回路構成・簡約の付随手法はいまだ知られていない。

関連項目

• テンプレート:仮リンク
• 論理ゲート
• ブール論理
• テンプレート:仮リンク