Exponential Complexity of NP-complete Problems

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

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.