Duality between Complexity and Algorithms

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

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