5.1 电路复杂性（Circuit Complexity）

文档摘要

5.1 电路复杂性（Circuit Complexity） 5.1 电路复杂性（Circuit Complexity）在现代计算范式下，复杂性理论已从图灵机的均匀抽象转向更精细的资源模型，电路复杂性便如同一座桥梁，连接了算法的理想化描述与实际硬件实现的残酷现实。试想一下：一台图灵机能以多项式时间解码NP问题吗？这仍是悬而未决的谜题。但当我们转向电路——一种静态、非均匀的计算架构时，问题顿时变得棘手起来。电路复杂性研究布尔电路的大小与深度，这些参数直接映射到芯片设计的门电路数量和信号传播延迟。它不仅挑战了$P$类的边界，还揭示了并行计算的本质极限。本节将系统剖析这一框架的核心，从布尔电路模型入手，揭示其与$P/poly$类的深刻关联；继而探讨Shannon定理如何奠定电路下界的基石；