回路（コンピュータサイエンス）

理論計算機科学において、回路とは、入力値が一連のゲートを通過し、各ゲートが関数を計算する計算モデルです。この種の回路は、ブール回路の一般化とデジタル論理回路の数学的モデルを提供します。回路は、含まれるゲートとゲートが生成できる値によって定義されます。たとえば、ブール回路の値はブール値であり、回路には論理積、論理和、否定ゲートが含まれます。整数回路の値は整数の集合であり、ゲートは集合の和集合、集合の積集合、集合の補集合、および算術演算の加算と乗算を計算します。

回路は3つ組で構成され、 ${\displaystyle (M,L,G)}$

• ${\displaystyle M}$値の集合であり、
• ${\displaystyle L}$はゲートラベルの集合であり、各ゲートラベルは非負の整数に対する関数である（ゲートへの入力数を表す）。${\displaystyle M^{i}}$${\displaystyle M}$${\displaystyle i}$${\displaystyle i}$
• ${\displaystyle G}$は、 からのラベルを持つラベル 付き有向非巡回グラフです。${\displaystyle L}$

グラフの頂点はゲートと呼ばれる。入次数の各ゲートに対して、が定義されている場合のみ、ゲートはの要素でラベル付けされる。${\displaystyle g}$ ${\displaystyle i}$${\displaystyle g}$${\displaystyle \ell}$${\displaystyle L}$${\displaystyle \ell}$${\displaystyle M^{i}.}$

入次数 0 のゲートは、入力またはリーフと呼ばれます。出次数 0 のゲートは、出力と呼ばれます。グラフにゲートからゲートへのエッジがある場合、は の子と呼ばれます。グラフの頂点には順序があると仮定すると、 がゲートの出次数以下の 場合、ゲートの 番目の子について話すことができます。${\displaystyle g}$${\displaystyle h}$${\displaystyle G}$${\displaystyle h}$${\displaystyle g}$${\displaystyle k}$${\displaystyle k}$

回路のサイズは、回路のノードの数です。ゲートの深さは 、出力ゲートまでの最長パスの長さです。特に、出力次数 0 のゲートは深さ 1 のゲートのみです。回路の深さは、ゲートの最大深さです。 ${\displaystyle g}$${\displaystyle G}$${\displaystyle g}$

レベルは${\displaystyle i}$、すべての深さのゲートの集合です。レベル化された回路は、深さのゲートへのエッジが深さのゲートまたは入力からのみ来る回路です。言い換えると、エッジは回路の隣接するレベル間にのみ存在します。レベル化された回路の幅は、任意のレベルの最大サイズです。 ${\displaystyle i}$${\displaystyle i}$${\displaystyle i+1}$

入次数とラベルを持つゲートの正確な値は、すべてのゲートに対して再帰的に定義されます。 ${\displaystyle V(g)}$${\displaystyle g}$${\displaystyle i}$${\displaystyle l}$${\displaystyle g}$

${\displaystyle V(g)={\begin{cases}l&{\text{if }}g{\text{ is an input}}\\l(V(g_{1}),\dotsc ,V(g_{i}))&{\text{otherwise,}}\end{cases}}}$

ここで、それぞれはの親です。 ${\displaystyle g_{j}}$${\displaystyle g}$

回路の値は各出力ゲートの値です。

葉のラベルは、 で値を取る変数にすることもできます。葉がある場合、回路は から への関数として見ることができます。その場合、回路のファミリ、つまり回路が変数を持つ整数でインデックス付けされた回路のシーケンスを考慮するのが一般的です。したがって、回路のファミリは からへの関数として見ることができます。 ${\displaystyle M}$${\displaystyle n}$${\displaystyle M^{n}}$${\displaystyle M}$${\displaystyle (C_{n})_{n\in \mathbb {N}}}$${\displaystyle C_{n}}$${\displaystyle n}$${\displaystyle M^{*}}$${\displaystyle M}$

サイズ、深さ、幅の概念は、関数の族に自然に拡張でき、 から までの関数になります。たとえば、は族の 番目の回路 のサイズです 。${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {N} }$${\displaystyle サイズ(n)}$${\displaystyle n}$

特定の入力に対して与えられたブール回路の出力を計算することはP 完全問題です。ただし、入力が整数回路の場合、この問題が決定可能かどうかは不明です。

回路の複雑さは、ブール関数を計算できる回路のサイズまたは深さに基づいて ブール関数を分類しようとします。

• 演算回路の複雑さ
• ブール回路
• 回路の複雑さ
• 自然数の集合上の回路
• 複雑性クラス NC、AC、TC
• 量子回路とBQP

• Vollmer, Heribert (1999)。回路の複雑さ入門。ベルリン: Springer。ISBN 978-3-540-64310-4。
• Yang, Ke (2001). 「整数回路の評価は PSPACE 完全です」. Journal of Computer and System Sciences . 63 (2, 2001 年 9 月): 288–303. doi : 10.1006/jcss.2001.1768 . ISSN  0022-0000.