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.