数独 爱好者？在深入了解游戏背后的数学原理后，在《大众科学》游戏专区用我们自己的谜题测试您的技能！SciAm Games!
计算机科学似乎正处于不可阻挡的进步曲线中。仅仅几十年，我们就从真空管发展到微芯片，从拨号上网发展到高速互联网，从Office助手 Clippy 发展到 ChatGPT。然而，科学和工业领域的成千上万个日常问题对于当今的人工智能超级计算机来说仍然像以往一样无法解决。
这些出了名的难题“NP完全问题”悬赏 百万美元奖金，由非营利组织克雷数学研究所颁发，奖励那些找到快速解决方案或证明不存在解决方案的人。20世纪70年代的一个惊人见解让这一挑战更具吸引力：那一千多个问题在深层意义上是同一个问题。如果您解决了一个，就解决了所有问题。这个概念现在是理论计算机科学领域的基础，它表明某些计算问题组形成了一个统一的网络。发现一种可以快速解决任何大小的 数独谜题 的算法，您现在就可以 破解保护我们数字经济的加密方案。揭示在预算内安排飞行旅行的捷径，您就可以用它来解决几乎任何著名的未解决 数学难题。
找到这些NP完全问题的快速算法（或证明不存在此类算法）将解决“P与NP”问题，这是计算机科学中最重要的谜题。P指的是计算机可以有效解决的计算问题集。同时，NP代表其解决方案可以有效验证的问题。但这些问题不一定能快速解决。NP包括P中的所有问题（因为找到解决方案是验证它的一个很好的方法），但也包括我们不知道有效方法来找到解决方案的更难的问题。我们只能在它们被解决后才能验证它们。P与NP问题询问，在找到解决方案和验证解决方案之间，这种明显的不对称性是真实存在还是虚幻的。也许P = NP，它们指的是同一组问题。换句话说，也许我们不知道如何有效解决的NP问题相对于P问题而言，只是因为我们尚未找到正确的见解而显得困难。
关于支持科学新闻
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道： 订阅。通过购买订阅，您正在帮助确保未来能够继续讲述关于塑造我们当今世界的发现和想法的具有影响力的故事。
例如，是否存在一种算法（一系列简单指令），给定任何大型城市列表、连接它们的航班以及预算，可以有效地决定您是否可以在预算范围内访问所有城市？我们不知道。我们确实知道一种低效的算法：检查访问所有城市的每种可能的航班顺序，将每种顺序的成本加起来，并将总成本与预算进行比较。但是，随着列表中的城市数量增加，要检查的路线数量呈指数级爆炸式增长，即使对于 最快的计算机 来说，也很快变得不可行。可能存在也可能不存在某种巧妙的捷径可以规避这种详尽的搜索，但计算机科学家尚未找到它。然而，给定一个解决方案——在本例中是一个拟议的航班列表——人们可以在合理的时间内验证一条路线是否访问了每个城市并在预算之内。如果P等于NP，这意味着航班场景（旅行商问题的示例）有一个快速的解决方案。我们只是还不知道。
许多自然的计算问题都与旅行商问题一起归入NP集。这包括来自物流（例如 将箱子装入卡车）、社交网络（寻找共同朋友的派系）、生物学（预测蛋白质如何折叠）以及游戏（如 数独、宝可梦 和 糖果粉碎传奇）的挑战。我们甚至可以将数学本身视为一个NP问题，因为它的证明可以有效地验证。当人们每天将箱子装入卡车并解决数独问题时，将这些问题归类为“难题”似乎很奇怪。但是，我们认为只有当算法能够有效地解决每个实例（包括非常大的实例）时，该算法才能有效地解决问题。“高效”的严格定义取决于解决问题所需的时间如何随着输入规模的扩大而扩展。当然，计算机解决9×9数独的速度比解决一百万乘一百万的数独要快，因此“高效”的严格定义取决于解决问题所需的时间如何随着输入规模的扩大而扩展。
P与NP问题涉及各种计算问题以及它们彼此之间的关系，因此，似乎需要单独研究每个问题才能解决这个问题。假设您发现了一种解决旅行商问题的有效算法。这将是一个英雄般的突破，但它是否会告诉您任何关于您解决巨型数独或任何其他具有挑战性的NP问题的能力的信息？令人惊讶的是，您解决该单个问题的算法将完全解决P与NP问题。1972年，计算机科学家理查德·卡普发表了一篇 开创性的论文，证明了21个经典的NP问题具有一个显著的特性：解决其中任何一个问题的有效算法不仅可以用于解决其他20个问题，而且可以用于解决NP中的每个问题。他将这21个问题称为NP完全问题。在随后的几年里，随着研究人员发现许多其他NP问题也具有这种神奇的特性（包括旅行商问题），这个列表变得越来越长。
我们可以用乐观或悲观的态度来看待NP完全性。从乐观的角度来看，横亘在我们与无限技术前景之间的一系列极其困难的问题现在看起来更像是一个纸牌屋。将其中一个问题拉入可行的领域，整个NP体系就会崩溃，一场科学革命将从废墟中升起，充满了轻松高效的旅行、通过蛋白质折叠快速 发现药物 以及数学的新时代。从悲观的角度来看，NP完全性表明这些问题没有有效的算法；如果证明事实并非如此只需要征服一个问题，那么为什么还没有人成功呢？大多数专家 倾向于 后一种解释，并怀疑NP完全问题没有快速算法。
无论以乐观还是悲观的角度来看待，完整问题的概念都改变了研究人员看待计算的方式。卡普表明，他可以使用解决一个NP完全问题的算法来解决另一个问题，首先要证明您可以使用称为“归约”的过程将看似无关的问题翻译成彼此的语言。其工作原理是展示如何获取一个问题的任何实例（例如，涉及城市列表、城市之间的航班和预算的问题），并将其转换为另一个问题（例如，大型 数独谜题），从而使数独谜题只有在可以在预算内访问所有城市时才具有有效解（否则没有有效解）。这样，如果您发现了一种解决数独问题的有效算法，那么您可以通过将旅行商问题的实例转换为数独谜题，使用该算法来解决旅行商问题。（请查看本文末尾，了解有关归约的详细示例。）
这种使用一种问题的语言来编码另一种问题的能力不仅是这个例子的怪癖，也是计算本身的一个特征。归约网络将所有NP完全问题联系在一起。解决其中任何一个问题，您就可以解决任何其他NP问题。其含义令人难以置信。请记住，我们可以将证明数学定理构架为一个NP完全问题。选择任何著名的未解决数学问题。NP完全性理论告诉我们，存在某个级别的 糖果粉碎传奇，它完美地编码了您的数学问题。如果在这个级别的糖果粉碎传奇中，在一定步数内可以达到一定的分数，那么您的数学问题就有一个特定长度的证明；否则就没有。NP完全性还向我们保证，蛋白质折叠（或箱子包装或数独求解）方面的某些进展将摧毁数字经济。这是因为保护我们敏感数据的加密是通过将它们隐藏在被认为难以解决的计算问题背后而工作的。（值得注意的是，虽然解决NP完全问题可以让您破解加密，但反之则不然；大多数加密方案背后的难解问题本身并不完全是NP完全问题。）
由于所有这些都与NP完全问题息息相关，因此一百万美元对于它们的解决方案来说可能看起来像是便宜货。下次当您努力安排假期旅行或破解数独谜题时，这可能会给您带来一些额外的动力。
归约是如何工作的？
对于任何想要更深入了解归约如何工作的人，让我们将另一种NP完全问题“地图三着色问题”归约到“团问题”。地图三着色问题 问道：给定一张地图，您能否为每个区域分配三种颜色之一，以使相邻区域不重复颜色？团问题则问道：给定一个社交网络，它是否包含一组所需数量的、彼此都是朋友的人？这两个问题都是NP完全问题，这意味着我们不知道任何解决它们的有效算法。表面上看，它们几乎没有共同之处。但我们将展示，给定一张地图，我们可以将其转换为社交网络，以便社交网络问题的答案将为我们提供地图问题的答案。
想象一下美国地图。为了从中构建一个社交网络，我们将为每个州指定三个“人”，每种颜色（蓝色、绿色和红色）各一个。然后，我们将使两个人成为朋友，除非：
他们代表同一个州。（威斯康星州的绿色代表不会与威斯康星州的蓝色代表成为朋友。）
他们具有相同的颜色并代表相邻的州。（北达科他州和南达科他州共享边界，因此它们的红色代表不会成为朋友，但北达科他州和佛罗里达州不相邻，因此它们的红色代表将成为朋友。）
我声明，只有当美国地图具有有效的三着色时，这个由150人组成的社交网络才会包含一个由50个共同朋友组成的团。如果我们在网络中找到了50个共同朋友，他们必须都代表不同的州，因为根据设计，当他们代表同一个州时，我们没有让他们成为朋友。此外，与团对应的着色永远不会为相邻州分配相同的颜色——我们明确禁止了网络中的此类链接。因此，一个由50人组成的团将对应于一个有效的三着色。同样，如果网络中不存在50-团，则地图也不存在三着色。
我们刚刚归约了地图三着色问题到团问题。这意味着，如果有人发现了解决团问题的快速算法，那么他们可以使用它来解决地图三着色问题的任何实例。至关重要的是，第一步——将地图转换为网络——是快速的。在网络中创建人和适当的友谊关系不需要任何详尽的搜索或其他不可行的计算开销。归约表明，即使我们的问题感觉是独一无二的，它们也可能比它们看起来更具普遍性。
这是一篇观点和分析文章，作者或作者表达的观点不一定代表《大众科学》的观点。