Circuit Complexity
Circuit Complexity（回路計算量）とは、計算理論の一分野で、ある計算問題を解くために必要な「論理回路」のサイズや深さを研究する学問です。
通常の計算量理論（PやNPなど）が「プログラムの実行時間やメモリ使用量」を測るのに対し、回路計算量は「ハードウェア的なリソース」で計算の難しさを評価します。
1. 基本的な考え方
計算問題を、論理ゲート（AND, OR, NOTなど）を組み合わせたboolean algoridhmによる論理回路として表現します。
- 入力: ビット列 (x1, x2, …, xn)
- 出力: 0 または 1（判定問題の場合）
2. 評価の指標
主に以下の2つの指標で「難しさ」を測ります。
- サイズ (Size):回路に含まれる論理ゲートの総数。これは、アルゴリズムの「実行時間」に対応します。
- 深さ (Depth):入力から出力までの最長パスにあるゲートの数。これは、並列計算における「処理時間」に対応します（ゲートを並列に並べれば、深さが浅いほど早く終わるため）。
3. 回路計算量の特徴
固定された入力サイズ
通常のプログラム（チューリングマシン）は、どんな長さの入力も1つのプログラムで処理しますが、回路は入力サイズ n ごとに異なる回路を考えます。
- 入力が10ビットなら10ビット用の回路
- 入力が100ビットなら100ビット用の回路
これらをまとめたものを「回路族（Circuit Family）」と呼びます。
P vs NP へのアプローチ
回路計算量は、計算理論の最難関である「P ≠ NP」を証明するための強力な武器になると期待されてきました。
もし「NPに属する問題が、多項式サイズの回路では絶対に解けない」ことを証明できれば、自動的に P≠ NPが証明されるからです。
4. 主要なクラス
回路計算量には、以下のような特有のクラスが存在します。
| クラス | 説明 |
| P/poly | 多項式サイズの回路で解ける問題の集合。 |
| NC (Nick’s Class) | 多項式サイズのゲート数で、かつ深さが対数スケール（$\log n$ の多項式）で解ける問題。並列計算が得意な問題群。 |
| AC0 | 深さが一定（定数）で、ゲートへの入力数に制限がない回路。非常に限定的な計算能力。 |
Circuit Complexityの目的は計算の限界を物理的に捉え直すことです。
現在のコンピュータ科学では、特定の複雑な関数（暗号の解読など）に対して「これだけの数のゲートを使わないと絶対に解けない」という下界（Lower Bound）を証明することが大きな目標となっています。しかし、一見単純そうな「NP 困難な問題には巨大な回路が必要だ」という証明は、現代の数学をもってしても非常に困難な課題です。