Average-Case Lower Bounds in Boolean Circuit Complexity

布尔电路复杂性的平均情况下限

• 批准号: RGPIN-2016-06467
• 负责人: Rossman, Benjamin
• 金额: $ 3.13万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=688593
• 关键词: Average; Case; Lower; Bounds; Boolean

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.***With the aim of developing sharper insights and techniques, the majority of the research in Circuit Complexity has focused on restricted classes of Boolean circuits (such as formulas, bounded-depth circuits, and monotone circuits). Following a burst of seminal lower bounds in the 80's and 90's, progress slowed as the existing techniques appeared to reach their limits. The “Natural Proofs barrier” of Razborov and Rudich (1997) identifies a formal roadblock to further progress by showing that lower bounds against more powerful classes of Boolean circuits can only proceed from techniques that are honed to specific hard-to-compute functions, while avoiding the generic properties shared by almost all functions.***This research proposal aims for a major advance in Circuit Complexity through a set of new techniques tailored to fundamental problems including CLIQUE and STCONN. One promising approach, introduced in previous work of the author, provides a combinatorial explanation of why small Boolean formulas fail to detect long paths in ErdosRényi random graphs. This approach has already produced groundbreaking lower bounds. The proposed research will pursue a sequence of next steps, with the ambitious goal of proving a super-polynomial lower bound against Boolean formulas. This would resolve a significant open problem in Complexity Theory (separating NC1 from P). Alongside this ambitious goal, this proposal explores other promising directions of research in Boolean circuit complexity and connections to areas such as proof complexity and communication complexity.**

复杂性理论研究有效计算的本质和限制。最终的目标是下界，表明基本问题，如CLIQUE和STCONN，不能用有限的计算资源，如多项式时间或对数内存来解决。电路复杂性的子领域旨在证明计算的组合模型中的下限。在这些模型中，布尔电路（由AND、OR和NOT门组成）是最基本和最重要的，因为它们提供了解决P与NP问题的具体途径：人们只需要证明CLIQUE问题（或NP中的任何其他问题）的超多项式电路大小下限。然而，经过60多年的努力，已知的最强下限只是线性的。为了开发更清晰的见解和技术，电路复杂性的大部分研究都集中在布尔电路的限制类（如公式，有界深度电路和单调电路）。在80年代和90年代出现了一系列开创性的下限之后，随着现有技术似乎达到了极限，进展放缓。Razborov和Rudich（1997）的“自然证明障碍”指出了进一步发展的正式障碍，表明针对更强大的布尔电路类的下界只能从特定的难以计算的函数的技术中进行，同时避免几乎所有函数共享的通用属性。这项研究提案旨在通过一套针对CLIQUE和STCONN等基本问题量身定制的新技术，在电路复杂性方面取得重大进展。一个有前途的方法，介绍了作者以前的工作，提供了一个组合的解释，为什么小布尔公式无法检测到长路径ErdosRényi随机图。这种方法已经产生了突破性的下限。拟议的研究将采取一系列后续步骤，其雄心勃勃的目标是证明针对布尔公式的超多项式下界。这将解决复杂性理论中一个重要的开放问题（将NC 1与P分离）。除了这个雄心勃勃的目标，该提案还探索了布尔电路复杂性的其他有前途的研究方向，以及与证明复杂性和通信复杂性等领域的联系。