为什么我需要关心这个问题？

在前面的章节中，我们研究了一些无需使用暴力搜索即可找到解的问题。然而，也存在一些问题，必须穷尽整个可能的搜索空间才能找到答案。以质因数分解为例，下面展示了数字 21 的质因数：

$7*3=21$

验证这个解很容易：只需将 7 和 3 相乘，检查结果是否等于 21 即可。但当我们想反过来操作——即找出 21 的质因数时——就必须从 1 开始逐一尝试除法，直到最终找到这些质因数。

$?*?=21$

对于像 21 这样的较小数字，暴力算法能在合理时间内完成。但对于如下所示的极大数字呢？

$?*?=213423567,890182215,329123767,110140235$

以当前的计算机技术而言，暴力算法无法在合理时间内求出上述大数的质因数。你可能会疑惑这为何重要。这就引出了密码学！加密算法正是利用了这样一个事实：两个极大的质数相乘很容易，但将乘积重新分解为原始的质因数却非常困难。如果质因数分解问题找到了高效的解法，那么目前工业界广泛依赖的许多加密算法都将被破解。

其影响远不止于密码学领域。迄今为止，即使使用现有的算法设计技术，人类仍未能为许多问题找到高效解法。一旦这些问题获得高效解决方案，将在医学、人工智能等众多领域带来重大突破。

复杂性理论学家根据解决问题的难易程度，定义了不同的复杂性类别。接下来的章节中，我们将简要介绍其中一些重要的类别。但在开始学习复杂性类别之前，我们先讨论“判定问题”，它有助于我们定义部分复杂性类别。

判定问题

一个判定问题是能够回答“是”或“否”的问题。算法本身并不是判定问题。例如，广度优先搜索算法在任何意义上都不是一个判定问题。本课程所讨论的复杂性类别仅包含判定问题。幸运的是，我们可以将算法转化为判定问题，以便分析其复杂性。例如，对于深度优先搜索，我们可以提出这样一个问题：能否在一个无环图中，通过最多访问每个节点一次来遍历所有节点？我们可以通过运行 DFS 并记录已访问节点的数量，在最后给出“是”或“否”的答案。

优化问题

从复杂性理论的角度来看，优化问题是一类非常有趣的问题。例如，在给定图中找出两个顶点之间的最短距离。两点之间可能存在多条路径，但最优解必须是最短的那一条；而且，最短路径也可能有多条。我们可以将最短路径问题转化为一个判定问题：在某个图中，是否存在一条连接两个顶点且边数少于 k 的路径？

如果我们能回答某个优化问题的判定版本，也就意味着我们能解决该优化问题本身。考虑从一个任意的边数 k 值开始，判定问题会给出“是”或“否”的答案。根据这一结果，我们可以调整 k 的值，并递归地应用二分查找，逐步逼近最优解。本质上，我们是将判定问题的解法嵌套在二分查找之中，从而得到优化后的结果。