难题的简短指南 (2018)

一个问题到底有多难？这是计算机科学家的基本任务，他们希望将问题分类为所谓的复杂性类别。这些是包含所有计算问题的组，这些问题需要的计算资源少于某个固定数量的计算资源——比如时间或内存。以具有大量数字的玩具为例，例如 123,456,789,001。有人可能会问：这个数是不是只能被 1 和它本身整除的质数？计算机科学家可以使用快速算法来解决这个问题——算法不会因为数字变得任意大而陷入困境。在我们的例子中，123,456,789,001 不是素数。那么我们可能会问：它的主要因素是什么？这里不存在这么快的算法——除非你使用量子计算机。因此计算机科学家认为这两个问题属于不同的复杂性类别。存在许多不同的复杂性类别，但在大多数情况下，研究人员无法证明一个类别与其他类别在绝对意义上是不同的。证明这些类型的分类区别是该领域最困难和最重要的开放问题之一。这就是为什么我上个月在 Quanta 上写的新结果被认为如此重要：在 5 月底发表的一篇论文中，两位计算机科学家证明（但有警告）代表量子计算机和经典计算机的两个复杂性类别确实是不同的。复杂性类别之间的差异可能很微妙，也可能很明显，并且保持类别一致是一个挑战。出于这个原因，广达将这本入门书放在了七个最基本的复杂性类别中。愿你永远不要再混淆 BPP 和 BQP。简短版本：经典（即非量子）计算机易于解决的所有问题。精确版本：P 中的算法必须在最多 nc 时间内停止并给出正确答案，其中 n 是输入的长度，c 是某个常数。典型问题： • 数是素数吗？ • 两点之间的最短路径是什么？研究人员想知道的是：P 和 NP 是一回事吗？如果是这样，它将颠覆计算机科学并使大多数密码学在一夜之间失效。 （几乎没有人认为是这种情况。）

简短版本：一旦给出解决方案，所有可以通过经典计算机快速验证的问题。精确版本：如果给出“是”的答案，有一个简短的证据证明答案是正确的，那么这个问题就是 NP。如果输入是一个字符串 X，并且您需要确定答案是否为“是”，那么一个简短的证明将是另一个字符串 Y，它可用于在多项式时间内验证答案确实是“是”。 ” （ Y 有时被称为“短见证”——NP 中的所有问题都有“短见证”，可以让它们快速得到验证。）典型问题： • 集团问题。想象一个带有边和节点的图——例如，一个图，其中节点是 Facebook 上的个体，如果两个节点是“朋友”，则它们通过一条边连接。一个集团是这个图的一个子集，其中所有人都是其他人的朋友。有人可能会问这样的图表：有20人的集团吗？ 50人？ 100？找到这样的一个团是一个“NP-完全”问题，这意味着它在 NP 中的任何问题中都具有最高的复杂性。但是如果给出一个潜在的答案——一个由 50 个节点组成的子集，可能会或可能不会形成一个集团——很容易检查。 • 旅行商问题。给定每对城市之间距离的城市列表，是否有办法在少于一定英里数的时间内穿越所有城市？例如，旅行推销员能否在不到 11,000 英里的范围内穿过美国的每个州首府？研究人员想知道什么：P = NP 吗？计算机科学家远未解决这个问题。简短版本：PH 是 NP 的概括——它包含了你从 NP 中的问题开始并添加额外的复杂层时遇到的所有问题。精确版本：PH 包含一些交替“量词”的问题，使问题更加复杂。这是一个交替量词问题的例子：给定 X，是否存在 Y 使得对于每个 Z 都存在 W 使得 R 发生？一个问题包含的量词越多，它就越复杂，它在多项式层次结构中的位置就越高。典型问题： • 确定是否存在大小为 50 的团但不存在大小为 51 的团。

研究人员想知道的是：计算机科学家一直无法证明 PH 与 P 不同。这个问题等价于 P vs NP 问题，因为如果（意外地）P = NP，那么所有的 PH 都会坍缩为 P（即, P = PH)。简短版本：PSPACE 包含可以用合理的内存量解决的所有问题。精确版本：在 PSPACE 中，您不关心时间，您只关心运行算法所需的内存量。计算机科学家已经证明，PSPACE 包含 PH，其中包含 NP，其中包含 P。 精确版本：量子计算机可以在多项式时间内解决的所有问题。研究人员想知道的：计算机科学家已经证明了 BQP 包含在 PSPACE 中，BQP 包含 P。不是 BQP，反之亦然。简短版本：经典计算机可以在指数时间内解决的所有问题。精确版本：EXP 包含所有以前的类——P、NP、PH、PSPACE 和 BQP。研究人员已经证明它与 P 不同——他们在 EXP 中发现了 P 中没有的问题。

典型问题： • 国际象棋和跳棋等游戏的泛化在 EXP 中。如果棋盘可以是任意大小，那么确定哪位棋手在给定棋盘位置上具有优势就成为 EXP 中的问题。研究人员想知道的是：计算机科学家希望能够证明 PSPACE 不包含 EXP。他们认为在 EXP 中存在 PSPACE 中没有的问题，因为有时在 EXP 中您需要大量内存来解决问题。计算机科学家知道如何区分 EXP 和 P。 简短版本：可以通过包含随机性元素的算法快速解决的问题。精确版本：BPP 与 P 完全相同，但不同之处在于该算法允许包含其决策随机化的步骤。 BPP 中的算法只需要以接近 1 的概率给出正确答案。 典型问题： • 您得到两个不同的公式，每个公式生成一个包含许多变量的多项式。这些公式是否计算完全相同的多项式？这称为多项式身份测试问题。研究人员想知道什么：计算机科学家想知道 BPP = P 是否正确。如果这是真的，这意味着每个随机算法都可以去随机化。他们认为情况确实如此——对于每个存在有效随机算法的问题，都有一个有效的确定性算法——但他们还没有能够证明这一点。