回路計算量
入力が n ビットの論理回路は有向非環状グラフであり、各ノード(回路計算量の場合、「ゲート」と呼ぶ)は、入次数 0 の入力ノード(n個の入力ビットのいずれかに対応)か、ANDゲート、ORゲート、NOTゲートである。これらのゲートのいずれかが出力ゲートとなる。このような回路が n 個の入力の関数を計算する。回路の大きさは、全ゲート数と、入力ゲートから出力ゲートまでの最大の長さ(すなわち、回路の深さ)で表される。
ブール関数 f の回路計算量(大きさと深さ)は、f を計算する回路のうちで最も小さい回路(あるいは浅い回路)の大きさ(や深さ)で表される。回路計算量の目標は、ブール関数群の最小の大きさや深さを決定することである。n ビット入力の関数 f n {\displaystyle f_{n}} の回路計算量を求める場合、 f 1 , f 2 , . . . {\displaystyle f_{1},f_{2},...} といった小さい関数から始めて、漸近的に求める手法がよく使われる。
論理回路に関する複雑性クラスとして、AC、AC、TC、NCがある。