Connections Between Algorithm Design and Complexity Theory

算法设计与复杂性理论之间的联系

• 批准号: 1540284
• 负责人: Richard Karp
• 金额: $ 2.5万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-01 至 2016-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1540284&HistoricalAwards=false
• 关键词: Connections; Between; Algorithm; Design; Complexity

Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. Complexity theory has the potential to become a real guide for algorithm design, identifying precisely what algorithmic performance is obtainable. A fundamental model of computation is the Boolean circuit, composed of interconnected logic gates. Complexity theory studies the capabilities of Boolean circuits when limits are placed on circuit size and circuit depth.  Recently, in what seems to be a paradox, breakthroughs on lower bounds in circuit  complexity  have been derived from the discovery of remarkably efficient algorithms.  The precise time complexity of SATISFIABILITY and other NP-complete problems is now linked to progress on a variety of fundamental questions in the theory of computation, many in surprising and counter-intuitive ways. These connections involve the exact complexity of basic polynomial-time solvable problems such as matrix multiplication and triangle detection.The workshop, which will be open to the public,  will gather researchers from computational complexity and algorithm design to discuss and extend these new developments.  This workshop will foster discussions that could lead to new algorithmic ideas for basic problems (often utilizing techniques from lower bounds), as well as new circuit lower bounds (utilizing improved algorithms). Students will be encouraged to participate in the workshop.

复杂性理论通过NP完全性等概念，区分了具有相对有效解的计算问题和难以处理的计算问题。复杂性理论有可能成为算法设计的真实的指南，精确地识别可以获得的算法性能。 计算的基本模型是布尔电路，由互连的逻辑门组成。复杂性理论研究了布尔电路在电路尺寸和电路深度受到限制时的能力。最近，在一个似乎是悖论的地方，在电路复杂度下限上的突破是由于发现了非常有效的算法。现在，完整的问题与计算理论中各种基本问题的进展联系在一起，许多问题以令人惊讶和违反直觉的方式出现。这些联系涉及基本多项式时间可解问题的精确复杂性，如矩阵乘法和三角形检测。该研讨会将向公众开放，将聚集来自计算复杂性和算法设计的研究人员，讨论和扩展这些新的发展。该研讨会将促进讨论，可能导致基本问题的新算法思想（通常利用来自下界的技术）以及新的电路下界（利用改进的算法）。 将鼓励学生参加研讨会。