回路値問題

回路値問題(または回路評価問題) は、与えられた入力に対して 与えられたブール回路の出力を計算する計算問題です。

この問題は、均一なAC ⁰削減の下でPに対して完全です。時間計算量の観点から、単純にトポロジカルソートによって線形時間で解決できることに注意してください。

ブール式値問題（またはブール式評価問題）は、回路が木の場合の特殊なケースです。ブール式値問題はNC ¹に対して完全です。^[1]

この問題は、 NPに対して完全なブール充足可能性問題、およびその補完問題であるco-NPに対して完全な命題トートロジー問題と密接に関連しています。

• 回路の充足可能性
• スイッチング補題

• Richard E. Ladner (1975 年 1 月)。 「回路値問題は P に対して対数空間完全である」。ACM SIGACTニュース。7 (101): 18–20。doi :10.1145/990518.990519。