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.