Quantifying Intractability and the Complexity of Heuristics

搜索和优化问题是计算机科学和工程所有领域的核心。寻找超大规模集成电路的最佳布局或晶体的最低能量配置都是优化问题的例子。虽然这些问题被认为是棘手的，需要指数时间来解决最坏情况，许多启发式方法已被观察到是相对成功的情况下，出现在不同的应用。本项目解决的问题，定量措施的棘手性，搜索和优化问题，而不是定性的概念，如NP完全性。 以下是本项目中解决的一些问题：1。哪些优化问题是最难处理的？2.这些问题到底有多难？ 3.解决最优化问题的好的启发式方法有哪些？ 它们何时以及如何发挥作用？ 4.像保理这样的特定非完全问题也是棘手的吗？ 5.随机性对解决问题有多大帮助？6.困难问题适合密码学应用吗？如果是，他们为这些应用程序提供了什么级别的安全性？这些问题的无条件答案首先需要解决P=NP问题。然而，本项目将使用两种方法来找到这些问题最可能的答案。 第一种方法是在合理的复杂性假设下提供解决这些问题的证据。 第二种方法是检查受限但功能强大的算法类别，其中包括研究中最成功的算法。这种方法将包括试图解释这种方法的成功，并显示可以作为问题可能的内在复杂性的指导的局限性。

Search and optimization problems are central to all areas of computer scienceand engineering. Finding the optimal layout for a VLSI circuit or the lowest energy configuration of a crystal are both examples of optimization problems.While such problems are believed to be intractable, requiring exponential time to solve the worst-case instances, many heuristic methods have been observed to be relatively successful on instances that arise in different applications.This project addresses questions concerning the quantitative measures of the intractability of search and optimization problems, as opposed to qualitative notionssuch as NP-completeness. The following are some of the questions addressed in this project:1. Which instances of optimization problems are the most intractable ones?2. Exactly how difficult are these problems? 3. What are good heuristic methods for solving optimization problems ? When and how well do they work? 4. Are specific non-complete problems such as factoring also intractable? 5. How much does randomness help in solving problems? 6. Are hard problems suitable for cryptographic applications?If so, what levels of security do they provide these applications? Unconditional answers to these questions first require solving the P=NP problem. However, this project will use two approaches to find the most likely answers to these questions. The first approach is to provide proofs resolving these issues underplausible complexity assumptions. The second approach is to examine restricted but powerful classes of algorithms that include the most successful heuristics for the problemsunder study. This approach will include attempts to both explain the success of such heuristics and to show limitations that can be used as a guide for the likely inherentcomplexity of the problems.