电路复杂度（Circuit Complexity）

电路复杂度（Circuit Complexity）是计算复杂度理论的一个分支，用布尔电路而非图灵机作为计算模型，以电路所含逻辑门的数量（规模）和最长路径（深度）来度量计算一个布尔函数的难易程度。

概述

布尔电路由与、或、非等逻辑门通过有向无环图连接而成，输入为若干比特，输出为函数值。每个固定长度的输入对应一个电路，因此电路模型是非均匀的——不同输入规模可用完全不同的电路。规模刻画所需硬件量，深度则对应并行计算的层数。

核心特点

• 非均匀性：每个输入长度可有独立电路，无需统一的有限描述。
• 规模：电路中逻辑门的总数，对应顺序计算的工作量。
• 深度：从输入到输出的最长门链长度，对应并行时间。
• 电路类：如AC0、NC1、TC0等，按深度、门类型与扇入限制划分。

核心原理

电路复杂度的一个核心动机是逼近P对NP等分离问题：若能证明某个NP问题不能由多项式规模电路计算，就推出P不等于NP。研究者已取得若干里程碑，如证明奇偶函数不属于AC0（常数深度、无界扇入电路），揭示了并行浅层电路的固有局限。然而对一般多项式规模电路证明超线性下界至今仍极为困难，是复杂度理论的重大挑战。

应用场景

电路复杂度用于分析并行算法能力、硬件设计中的资源估算、密码学中伪随机函数的构造，以及为P对NP、NP对P/poly等分离问题提供技术路线。NC类刻画了可高效并行的问题，TC0则与神经网络等阈值计算模型密切相关。

常见问题

问：电路模型和图灵机模型有何本质区别？答：图灵机是均匀模型，一台机器处理所有输入长度；电路是非均匀模型，每个长度可用不同电路，因此电路族甚至能计算某些不可判定问题。

问：为什么用电路研究P对NP？答：因为多项式规模电路类P/poly包含P，若能证明某NP问题需要超多项式规模电路，就可推出P不等于NP，这是一条被寄予厚望的攻坚路径。