回路計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/18 03:59 UTC 版)
回路計算量（英: circuit complexity）とは、計算複雑性理論において、ブール関数をその計算に要する計算資源の量によって分類することを指す。回路計算量では、それらの資源量は論理回路の大きさや深さで表される。
概要
入力が n ビットの論理回路は有向非巡回グラフであり、各ノード（回路計算量の場合、「ゲート」と呼ぶ）は、入次数 0 の入力ノード（n個の入力ビットのいずれかに対応）か、ANDゲート、ORゲート、NOTゲートである。これらのゲートのいずれかが出力ゲートとなる。このような回路が n 個の入力の関数を計算する。回路の大きさは、全ゲート数と、入力ゲートから出力ゲートまでの最大の長さ（すなわち、回路の深さ）で表される。
ブール関数 f の回路計算量（大きさと深さ）は、f を計算する回路のうちで最も小さい回路（あるいは浅い回路）の大きさ（や深さ）で表される。回路計算量の目標は、ブール関数群の最小の大きさや深さを決定することである。n ビット入力の関数 
- 回路計算量のページへのリンク
