Exponential Complexity of NP-complete Problems

NP 完全问题的指数复杂度

• 批准号: 0947262
• 负责人: Ramamohan Paturi
• 金额: $ 20万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-01 至 2012-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0947262&HistoricalAwards=false
• 关键词: Exponential; Complexity; NP; complete; Problems

This project supports research by Paturi, his graduate students and collaborators on foundational questions about the exact complexity of NP-complete problems The core questions addressed concern the difficulty of exhaustive search, and to what extent an exhaustive search may be pruned to improve its effectiveness. The project will study the complexity of algorithms, especially for the fundamental problem of satisfiability, but also for other NP-complete problems such as the traveling salesman problem and k-colorability. The PI and his students will study probabilistic search algorithms that succeed with exponentially small probability. They will study self-reducibility among instances of the circuit satisfiability problem as well as the fundamental question of trade-off between time and probability for NP-complete problems.Research on exact exponential-time algorithms for NP-complete problems not only has the potential to improve our understanding of fundamental limitations of feasible computability, but may possibly lead directly to new algorithms for satisfiability and other combinatorial optimization problems. The project will support graduate student education and research in computer science, especially in algorithms and complexity theory. The PI engages in teaching at the undergraduate and graduate level in computer science that will benefit from his research activities supported by the project.

该项目支持 Paturi、他的研究生和合作者关于 NP 完全问题的确切复杂性的基本问题的研究。解决的核心问题涉及穷举搜索的难度，以及穷举搜索在多大程度上可以被修剪以提高其有效性。该项目将研究算法的复杂性，特别是可满足性的基本问题，但也会研究其他 NP 完全问题，例如旅行商问题和 k-可着色性。 PI 和他的学生将研究以指数级小概率成功的概率搜索算法。 他们将研究电路可满足性问题实例之间的自约性，以及 NP 完全问题的时间和概率之间权衡的基本问题。对 NP 完全问题的精确指数时间算法的研究不仅有可能提高我们对可行可计算性基本限制的理解，而且可能直接导致可满足性和其他组合优化问题的新算法。该项目将支持计算机科学领域的研究生教育和研究，特别是算法和复杂性理论方面的研究。 PI 从事计算机科学领域的本科和研究生教学，这将受益于该项目支持的研究活动。