Algorithms and complexity of hard problems: bridging the gap between theory and practice

算法学和人工智能领域的许多研究人员普遍认为，在实际领域中仍然缺乏关于各种计算困难的算法问题的理论。面向最坏情况的计算复杂性理论虽然对计算世界产生了巨大的影响，但在应用于现实世界问题的“典型”实例时，对许多实际算法的行为提供了急需的洞察力，这已被证明是不令人满意的。近年来，出现了一些新的范例，以帮助提高我们的能力，以科普棘手的算法问题。 其中有概率分析，如相变的研究和特定算法的平滑分析，参数化复杂性和算法的理论，以及精确（指数时间）算法的理论。

It is a widely-held belief among many researchers in algorithmics and artificial intelligence that there remains a lack of theory on the nature of various computationally-hard algorithmic problems in practical fields. The worst-case oriented theory of computational complexity, while having had an enormous impact to the computing world, has proven to be unsatisfactory for providing the much-needed insight into the behavior of many practical algorithms when applied to "typical" instances of real-world problems. In recent years, several new paradigms have emerged to help improve our ability to cope with the intractability of hard algorithmic problems. Among them are probabilistic analysis such as the study of phase transitions and the smoothed analysis of specific algorithms, the theory of parameterized complexity and algorithms, and the theory of exact (exponential-time) algorithms.