Duality between Complexity and Algorithms

复杂性和算法之间的二元性

• 批准号: 0515332
• 负责人: Russell Impagliazzo
• 金额: $ 20.16万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-15 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0515332&HistoricalAwards=false
• 关键词: Duality; between; Complexity; Algorithms

Intellectual Merit: Algorithm design investigates the most efficient ways to solve specific computational problems, whereas complexity theory investigates relationships between general classes of computational problems. This proposal will investigate situations in which answering questions in complexity require us to understand specific algorithmic problems, and designing efficient algorithms require us to answer questions in complexity. Recently, there have been several results that expose the connection between complexity and algorithms. Examples include the connections between algebraic circuit lower bounds and polynomial-identity testing, better exponential algorithms for _ -SAT and circuit lower bounds, limitations of widely used backtracking algorithms and proof complexity, and constructions of error-correcting codes and constructions of pseudorandom generators. The proposed work will elaborate on these connections between combinatorial constructions, efficient algorithms, and complexity. It will use these connections to further our understanding of both algorithms and complexity. It will also seek new connections in the study of randomness in computing, proof complexity, the exact complexity of N P-complete problems, and formal models of algorithm paradigms.This proposal will investigate issues where algorithm design is key to new results in complexity. Such issues include:_Which instances of optimization problems are the most intractable ones? Exactly how difficult are these problems?What are good heuristic methods for solving optimization problems? When and how well do they work?Can we distinguish between the powers of various general algorithmic methods (e.g., dynamic programming, greedy algorithms, back-tracking, local search, linear-programming relaxation) for solving these problems?How much does randomness help in solving problems?What is the relationship between the theory of sub exponential time algorithms and fixed parameter tractability? What other consequences would the existence of sub exponential algorithms have for complexity and cryptography?While complete answers to most of these questions will probably not be possible in the foreseeable future, researchers in complexity, including the PIs, have made substantial progress on all of them. In particular, it is becoming apparent that these questions are so interrelated that it is impossible to address any one issue in isolation. Instead, success will require a multi-pronged effort that reveals the interconnections, and uses progress in one direction to obtain similar progress on others.Broader Impact: Search and optimization are central to any computational issue in science and engineering. For example, finding the most probable folding of a protein, finding the smallest area of a VLSI chip, and finding the optimal way to classify data are all combinatorial optimization problems. The same algorithmic techniques are used to solve such problems in a wide variety of application domains. However, many of these techniques are heuristic in that factors that determine the performance are not well understood. This is more than academic issue since the lack of understanding prevents users from matching application areas to the most suitable algorithmic techniques. The work in this proposal is intended to further this understanding and hence may indirectly lead to improvements in many diverse application domains.This proposal will also train graduate students to be top researchers and educators like many of our alumni.1

智力优势：算法设计研究解决特定计算问题的最有效方法，而复杂性理论研究一般计算问题之间的关系。本提案将研究回答复杂问题需要我们理解特定算法问题的情况，以及设计高效算法需要我们回答复杂问题的情况。最近，有几个结果揭示了复杂性和算法之间的联系。例子包括代数电路下界与多项式恒等检验之间的联系，_ -SAT和电路下界的更好的指数算法，广泛使用的回溯算法的局限性和证明复杂性，以及纠错码的构造和伪随机生成器的构造。建议的工作将详细说明组合结构，高效算法和复杂性之间的这些联系。它将利用这些联系进一步加深我们对算法和复杂性的理解。它还将在计算中的随机性、证明复杂性、N - p完全问题的精确复杂性和算法范例的正式模型的研究中寻求新的联系。本提案将探讨算法设计是复杂性新结果的关键问题。这些问题包括：哪些优化问题的实例是最棘手的？这些问题到底有多难？什么是解决优化问题的好的启发式方法？它们何时起作用，效果如何？我们能否区分解决这些问题的各种通用算法方法（例如，动态规划、贪婪算法、回溯、局部搜索、线性规划松弛）的能力？随机性对解决问题有多大帮助？次指数时间算法理论与固定参数可跟踪性之间的关系是什么？亚指数算法的存在会对复杂性和密码学产生什么其他影响？虽然在可预见的未来，这些问题的完整答案可能是不可能的，但包括pi在内的复杂性研究人员已经在所有这些问题上取得了实质性进展。特别是，越来越明显的是，这些问题是如此相互关联，以致不可能孤立地处理任何一个问题。相反，成功将需要多管齐下的努力，揭示相互联系，并利用一个方向的进展在其他方面取得类似的进展。更广泛的影响：搜索和优化是科学和工程中任何计算问题的核心。例如，寻找蛋白质的最可能折叠，寻找VLSI芯片的最小面积，以及寻找数据分类的最佳方法都是组合优化问题。在各种各样的应用领域中，使用相同的算法技术来解决此类问题。然而，这些技术中的许多都是启发式的，因为决定性能的因素没有得到很好的理解。这不仅仅是一个学术问题，因为缺乏理解阻碍了用户将应用领域与最合适的算法技术相匹配。本提案中的工作旨在进一步理解这一点，因此可能间接导致许多不同应用领域的改进。这项计划还将把研究生培养成顶尖的研究人员和教育工作者，就像我们的许多校友一样