布尔电路与电路复杂性

布尔电路通过逻辑门网络计算函数，而电路复杂性通过解决问题所需的电路规模和深度来衡量问题，提供了计算的并行和硬件视角。

Definition

布尔电路是逻辑门的有向无环图，用于计算固定长度二进制输入的函数；电路复杂性研究计算给定布尔函数族所需的最小门数、深度或其他结构资源。

Scope

本主题涵盖布尔电路和公式、复杂性的规模和深度度量、均匀与非均匀模型、NC和AC等低深度类别、电路下界与复杂性类别分离之间的关系，以及受限电路族的里程碑式下界结果。

Core questions

• 计算的门网络视图与顺序机器有何不同？
• 电路规模和深度衡量什么？它们与时间和并行性有何关系？
• 为什么电路下界是分离复杂性类别的一种途径？
• 已知哪些下界？哪些障碍阻碍了更强的下界？

Key theories

非均匀性与P/poly类

电路允许为每个输入长度使用不同的机器，从而产生包含P的非均匀类P/poly；证明NP完全问题缺乏多项式规模电路将分离P与NP，从而推动了电路下界的研究。

受限电路的下界

对于受限族，已知存在强下界，例如计算奇偶校验的常数深度电路所需的指数规模，尽管一般电路的下界仍然遥不可及。

Clinical relevance

电路是数字硬件的自然模型，因此电路复杂性为芯片设计和并行计算的极限提供了信息；低深度类别捕捉了可以用许多处理器快速计算的内容，而电路下界是解决P与NP等问题的长期努力中的主要策略。

History

香农于1937年将布尔代数与开关电路联系起来，电路复杂性在20世纪80年代作为一门学科成熟起来，当时Furst、Saxe、Sipser等人证明了奇偶校验的常数深度下界，Razborov和Smolensky开发了代数方法，之后自然证明障碍揭示了为什么一般的下界如此难以捉摸。

Key figures

• Claude Shannon
• Alexander Razborov
• Andrew Yao
• Roman Smolensky

Seminal works

• aroraBarak2009
• vollmer1999

Frequently asked questions

电路与图灵机有何不同？

图灵机是处理所有大小输入并逐步执行的单一设备，而电路是针对单一输入长度的固定门网络，每个长度都有一个单独的电路。这种非均匀性使电路成为硬件和并行计算的自然模型，并且可以表达单一均匀机器无法表达的事物。

为什么研究人员关心电路下界？

证明NP中的一个问题需要非常大的电路将分离复杂性类别，并可能解决P与NP问题。对于受限电路族，已知存在下界，但将其扩展到一般电路受到形式障碍的阻碍，这使其成为该领域最深刻的开放挑战之一。