SIGACT News Complexity Theory Column 76: an atypical survey of typical-case heuristic algorithms
SIGACT News Complexity Theory Column 76: an atypical survey of typical-case heuristic algorithms
复制标题
SIGACT新闻复杂性理论专栏76：典型案例启发式算法的非典型调查
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Ryan Williams
中科院分区：
文献类型：
--
作者：
L. Hemaspaandra;Ryan Williams
启发式方法通常做得很好，它们似乎几乎总是给出正确的答案。启发式算法能在多大程度上总是给出正确的答案，而不会导致地震复杂性理论的后果？本文首先讨论了Berman、Buhrman、Hartmanis、Homer、Longpré、Ogiwara、Schöning和Watanabe在20世纪70年代初到90年代初的一系列结果，这些结果显式或隐式地限制了启发式算法在NP难问题上的表现。特别是，除非发生严重的、极不可能发生的复杂性类崩溃，否则无法获得许多理想的启发式成功水平。其次，我们调查工作发起的Goldreich和Wigderson，谁显示了如何在合理的假设下确定性随机计算可以实现一个非常高的正确率。最后，我们考虑正式的方法，理论可以帮助解释的有效性，解决NP难问题在实践中。
Heuristic approaches often do so well that they seem to pretty much always give the right answer. How close can heuristic algorithms get to always giving the right answer, without inducing seismic complexity-theoretic consequences? This article first discusses how a series of results by Berman, Buhrman, Hartmanis, Homer, Longpré, Ogiwara, Schöning, and Watanabe, from the early 1970s through the early 1990s, explicitly or implicitly limited how well heuristic algorithms can do on NP-hard problems. In particular, many desirable levels of heuristic success cannot be obtained unless severe, highly unlikely complexity class collapses occur. Second, we survey work initiated by Goldreich and Wigderson, who showed how under plausible assumptions deterministic heuristics for randomized computation can achieve a very high frequency of correctness. Finally, we consider formal ways in which theory can help explain the effectiveness of heuristics that solve NP-hard problems in practice.