Average-Case Lower Bounds in Boolean Circuit Complexity

复杂性理论研究有效计算的本质和限制。最终的目标是下界，表明基本问题，如CLIQUE和STCONN，不能用有限的计算资源，如多项式时间或对数内存来解决。电路复杂性的子领域旨在证明计算的组合模型中的下限。在这些模型中，布尔电路（由AND、OR和NOT门组成）是最基本和最重要的，因为它们提供了解决P与NP问题的具体途径：人们只需要证明CLIQUE问题（或NP中的任何其他问题）的超多项式电路大小下限。然而，经过60多年的努力，已知的最强下限只是线性的。

Complexity Theory studies the nature and limits of efficient computation. The ultimate goals are lower bounds showing that fundamental problems, such as CLIQUE and STCONN, cannot be solved with limited computational resources, such as polynomial time or logarithmic memory. The subfield of Circuit Complexity seeks to prove lower bounds in combinatorial models of computation. Among these models, Boolean circuits (composed of AND, OR and NOT gates) are the most elemental and important, as they offer a concrete path to resolving the P versus NP question: one need only prove a super-polynomial circuit-size lower bound for the CLIQUE problem (or any other problem in NP). However, after over 60 years of effort, the strongest known lower bounds are only linear.