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

难题的算法和复杂性：弥合理论与实践之间的差距

• 批准号: 327587-2009
• 负责人: Gao, Yong
• 金额: $ 1.38万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2012
• 资助国家: 加拿大
• 起止时间: 2012-01-01 至 2013-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=503365
• 关键词: Algorithms; complexity; hard; problems; bridging

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.

这是许多研究人员在算法和人工智能方面的广泛信念，即对实践领域的各种计算算法问题的本质仍然缺乏理论。最糟糕的计算复杂性理论对计算世界产生了巨大影响，但事实证明，当应用于“典型”现实世界问题的“典型”实例时，对许多实际算法的行为提供了急需的洞察力。近年来，已经出现了一些新的范式，以帮助提高我们应对硬算法问题的棘手性的能力。 其中包括概率分析，例如对相变的研究和特定算法的平滑分析，参数化的复杂性和算法的理论以及精确（指数时间）算法的理论。