Exponential Complexity of 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.