以及固有的难题

算法分析和O( )符号使得我们能够讨论一个特定算法的效率问题。然而，对于我们需要解决的问题，它们并没有告诉我们任何关于更好的算法究竟是否存在的信息。复杂性分析领域分析的是问题而不是算法。第一个十分明显的分界介于能够在多项式时间内解决的问题与无论使用什么算法也不能在多项式时间内解决的问题之间。多项式问题类——也就是那些对于某个 k 能够在O(nk)时间内解决的问题——被称为P。有时候这些问题也被称为“简单”问题，因为这个类中包含了那些运行时间类似O(log n)和O(n)的问题。不过它同样包含了时间为O(n1000)这样的问题，因此我们不能过于刻板地理解“简单”这个称谓。

另一个重要的问题类是 NP，即不确定多项式问题类。这个类中的问题是指存在某个算法能够在多项式时间内猜测出一个该问题的解并验证这个猜测是否正确。其思想是，如果你有任意多的处理器，从而你能够同时尝试所有的猜测，或者你非常幸运而总是在第一次就猜到了正确的解，那么 NP 问题就变成了P问题。计算机科学中最大的开放问题之一就是在既没有无限多的处理器也没有无所不知的猜测时，NP类是否等价于P类。绝大部分计算机科学家都确信P≠NP——NP问题是固有的难题，没有多项式时间算法。不过这一点还一直没有得到证明。

那些对判定P=NP有兴趣的人可以看看一个称为NP完全问题的NP子类。这里的“完全”是“最极端”的意思，因此它所指的是NP类中最难的问题。已经证明，要么所有的NP完全问题都是P问题，要么一个也不是。这使得分类在理论上很令人感兴趣，同时这类问题在现实中也很令人感兴趣，因为很多重要的问题都已知是 NP 完全的。一个例子是可满足性问题：给定一条命题逻辑语句，是否存在一种针对语句中命题符号的真值赋值方案使得该语句为真？除非P=NP的奇迹出现，否则不可能存在一种算法在多项式时间内解决所有的可满足性问题。不过，人工智能更感兴趣的是对于从预先确定的分布上抽取出的典型问题，是否存在能够有效执行的算法。如同我们在第七章中所看到的，存在诸如WALKSAT这样的算法，在很多问题上都工作得相当好。

余NP问题类在这样的意义下与NP问题是互补的：对于每一个NP决策问题，都有一个对应的余NP问题，其中“是”与“否”的回答正好反过来。我们知道，P问题既是NP问题的子类，也是余NP问题的子类，因此人们相信存在非P问题的余NP问题。余NP完全问题是余NP问题中最难的问题。

#P问题类（读作“sharp P”）（意思为“个数P”——译者注）是与NP决策问题相对应的计数问题集合。决策问题的答案为“是”或者“否”：对这个3-SAT公式是否存在一个解？而计数问题的答案是一个整数：满足这个3-SAT公式的解有多少个？在某些情况下，计数问题要比决策问题困难得多。例如，我们可以在时间O(V E)内确定一个二部图是否存在完全匹配（这个二部图具有V个顶点和E条边），但计数问题“这个二部图有多少个完全匹配”则是#P完全问题，这意味着它和任何#P问题一样难，因此至少也和任何NP问题一样难。

人们研究的另一类问题是PSPACE问题——那些需要多项式容量的空间的问题，即使在一台不确定的机器上。人们相信PSPACE难题比NP完全问题更糟糕，尽管可能会发现NP = PSPACE，正如可能会发现P = NP。