第1章 什么是NP问题

大部分的算法入门图书，包括“算法详解”系列图书的第1卷到第3卷，都存在选择性偏向的问题。它们关注的是能够由精巧、快速的算法所解决的计算性问题。不管怎么说，还有什么比学习一种精妙的快速算法更有乐趣、更有成就感呢？好消息是许多基本的、实用的问题都可以归入这个范畴，包括排序、图的搜索、最短路径、哈夫曼编码、最小生成树、序列对齐等。但是，如果只介绍这些精心选择的问题而忽略那些让严肃的算法设计师和程序员深感头痛的计算性难题，无疑是不客观和不全面的。遗憾的是，有很多重要的计算性问题，包括在我们的项目中经常出现的一些问题，并不存在已知的快速算法。更糟的是，我们无法期待解决这些问题的算法能够在未来得到突破，因为它们已经被公认存在死结，无法由任何快速算法所解决。

意识到这个严峻的事实之后，我们很快就会想到两个问题。首先，当这类问题在我们的工作中出现时，怎么才能认识到它们的存在，以便相应地调整自己的期望值，避免花费大量的时间寻找注定是美梦泡影的算法呢？其次，如果这类问题对于我们的应用是非常重要的，我们应该如何调整自己的期望值，应该使用什么算法工具来实现它们呢？本书将提供这两个问题的详细答案。