Quantifying Intractability and the Complexity of Heuristics

搜索和优化问题是计算机科学和工程所有领域的核心问题。寻找超大规模集成电路的最佳布局或晶体的最低能量配置都是优化问题的例子。虽然这样的问题被认为是难以解决的，需要指数级的时间来解决最坏情况，但许多启发式方法已经被观察到在不同应用中出现的实例上相对成功。这个项目解决了关于搜索和优化问题的难处的定量测量的问题，而不是定性的概念，如np完备性。以下是本项目解决的一些问题：哪一类优化问题是最棘手的？这些问题到底有多难？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.