Exact Algorithms and Complexity

摘要

Over the past couple of decades, a series of exact exponential-time algorithms have been developed with improved run times for a number of problems including IndependentSet, k-SAT, and k-colorability using a variety of algorithmic techniques such as backtracking, dynamic programming, and inclusion-exclusion. The series of improvements are typically in the form of better exponents compared to exhaustive search. These improvements prompt several questions, chief among them is whether we can expect continued improvements in the exponent. Is there a limit beyond which one should not expect improvement? If we assume NP ≠P or other appropriate complexity statement, what can we say about the likely exact complexities of various NP-complete problems?