从 P 到 NP 的复杂之路：解决方案空间的魔力

P（多项式时间）与 NP（非多项式时间）是一个解决特定问题空间的根本复杂性问题。例如，P 问题是一个解决时间以多项式时间增加的问题。我们有一个数字数组：[a、b、c、d、e、f、g]，任务是对这些数字进行排序。当前算法解决这个问题的方式是逐个遍历每个数字，如果当前数字小于最后一个数字（如果我们按升序排序），则将数字向后移动一个位置。我们向数组中添加的数字越多，完整排序所需的时间就越长。然而，这种增加是渐进的和可预测的。 NP 问题的问题复杂度要高得多。例如，这种 NP 问题就是“旅行商问题”（TSP）。该问题要求给定一张包含一定数量城市的地图：假设城市 [a、b、c、d、e、f、g]。目标是找到所有这些城市之间的最短路线。在这种情况下，我们添加的城市越多，找到解决方案所需的时间就会急剧增加。 为了更好地理解，想象一下，在 P 问题的情况下，时间的增加类似于加法，随着每个新数据添加到集合中，时间通过将数据集中找到的数据点的总和添加到当前时间而增加。例如，在我们的排序问题中，当我们有一个数字时，解决问题所需的时间为 1（不是 0，因为最后需要检查），并且随着第二个数字的添加，时间变为 1 + 2 = 3。第三个数字（+3）将时间增加到 6，第四个数字（+4）将时间增加到 10，依此类推。 对于 NP 问题，以 TSP 为例，对于每个新增城市，我们将新增城市的编号乘以当前所需时间。如果只有一个城市，则所需时间为 1；如果有两个城市，则所需时间为 1 x 2 = 2；如果有三个城市，则所需时间为 2 x 3 = 6。第四个城市所需时间为 6 x 4 = 24，以此类推。当然，这不是一个有效且现实的时间增加场景，但它是一种很好的方式，可以直观地了解随着 NP 问题的数据集相对于 P 问题的数据集增加，需要多少时间。 现在我们了解了这两种类型的问题，我们提出的问题是：P 是否等于 NP（意味着使用正确的工具和算法，我们可以在多项式时间内有效地解决每个问题，NP 或 P）或者它们不同（意味着复杂性是问题空间的固有属性，因此，无论我们的知识和理解变得多么先进，都存在着我们无法完全解决的问题）。 熟悉 P-NP 问题的人认为，它们本质上是不同的，而且有些问题我们可能永远无法有效解决。但是，如果不打破这两种问题类型之间的隔阂，我们的好奇心和理解力又是为了什么呢？ 在接下来的部分中，我将介绍我的观点以及我所发现的看待这个问题的角度。在本文结束时，我希望能够清楚地向您展示对这两个相互交织的问题空间的整体理解。 第一部分：简单对抗复杂 为了更好地理解问题的本质，我们将从哲学的角度来思考一下简单性和复杂性的本质。毕竟，如果复杂性最终不同于简单性，那么我们就可以简单而真实地假设，存在一些问题 (NP)，需要复杂的解空间 (即量子叠加性) 才能在多项式时间内解决问题。 对于 TSP 问题，复杂的解决方案空间表示一条解决方案路径，该路径考虑了所有城市及其各自的位置，并保留所有这些位置，以便找到城市之间的合理联系。但即使我们考虑了所有必要的权重，我们出发的城市与算法为找到最有效路线而执行的步行一样重要，对吗？如果我们从城市 a 出发，那么最有效的路径将呈现某种形状；如果我们从城市 b 出发，最有效的路径看起来会有所不同。 或者这可能是一个错误的推理。毕竟，最有效的路径是唯一的，并且最终是最有效的，因为它代表了所有城市之间的最短联系。我们不寻找从城市 a 到城市 b 的最短路径，而是寻找将所有城市联系在一起的最短路径。从这个角度来看，我们可以将最短路线形象化，类似于“崩溃”状态，其中城市之间的总距离最短。 如果我们使用“强力”算法来形成各种路径，然后对它们进行比较，那么所有这些路径都将是该算法的相同“强力”推理的结果，因此形成路径的每次实例最终都是线性推理。如果我们偶然找到最短路线，那么算法的“强力”和“机会”方面将无法知道该路线是否最终是最短的。 现在，这种方法似乎可以从机器学习的力量中受益，机器学习最终被训练来做出近似。想象一下，使用城市地图以及城市之间的最短路径来训练人工智能。这样，我们可以改用“有根据的猜测”算法，而不是“蛮力”算法，这将证明效率的明显提高。 哦，但是，我们仍然需要一种绝对的方法来找到最短的路径。而且到目前为止，还没有办法 100% 准确地知道我们面前的路径是否最短。从这个意义上讲，启发式方法和其他数学模型旨在提供对逻辑基础的理解，从而告诉我们最有效的路径。然而，这些方法目前还不完整，我们甚至不知道当它们完整时，它们是否仍然能够为我们提供最准确的答案，还是仅仅是“粗暴的”猜测。 第 2 部分：过于简单 我可能有点偏离了简单性和复杂性的话题。或者可能没有真正从哲学的角度来处理它们。从这个意义上讲，我所做的基本上就是问我们是否能以某种方式在我们的方法中达到一定的复杂性，以及一旦我们找到正确的解决方案，我们是否会得到“是”的答案。但是，由于最短路径存在于任何地图上，并且包含任意数量的城市，因此它必须具有特定的价值和特定的细节，使其脱颖而出，对吗？ 或者，也许这些细节只有在经过无数次不同路径的循环后，才会以总行程距离的形式出现。但这种假设可能根本不合理。毕竟，最短路径就是最短的，无论我们经过多少次。事实上，我们经过的循环越多，我们就越了解哪个更短，哪个更大。然而，这种推理可能只在我们想要用不够精确的测量工具区分原子级小循环的情况下才需要。 现在看来，问题不在于找到探究的真相，而在于我们用来测试真相的工具的能力。当要砍树时，我们使用斧头。当要听音乐时，我们使用耳机。当要形式化和理解数学时，我们使用逻辑构建的工具。 也许这就是数学的内在美。我们把一些简单的东西与另一个简单的东西融合在一起，它们一起形成了一个复杂的东西，例如，这使我们能够对角移动。或者画一个完美的圆圈之类的。但是，有多少个这样的简单工具可以相互绑定？在什么时候我们可以将两个复杂的工具混合在一起？如果可以，我们是否只能通过合并两个较低的复杂工具来实现更复杂的工具，或者也可以通过合并形成它们的所有较低的简单工具来实现更复杂的工具？ 从这个意义上讲，启发式方法就像那些工具，在相互作用中，我们可以找到一种方法来 100% 准确地回答我们是否找到了城市之间的最短路径。从这个角度来看，启发式方法就像一个解决方案证明器，但要找到解决方案，我们可能需要其他方法。归根结底，P 与 NP 的根源与复杂性本身的性质息息相关，因此我们必须问自己是否可以在单个线性时间内走两条（甚至更多）不同的路径。 第三部分：复杂性的分形本质 待在这里是一件很有趣的事。待在……那里。写作休息三十分钟后，我们会把接下来的想法以最佳顺序和最易理解的规模整理好。事实是，这些想法比以往任何时候都更清晰；它们甚至折叠成一个完整的闭合循环。然后，那个循环变成了一个点，成为了整体中一个闪亮的部分，它之所以闪亮，并不是因为它相对于整个系统来说有什么特别之处，而是因为它是当前的空间、当前的理解，以及我们所处的位置。当我们向上看的时候，我们会发现复杂和简单。当我们向下看的时候，我们会发现同样的东西。当我们向侧面看的时候，也没有什么不同。 这样，我们确实找到了我们想要的东西。如果我们寻找 NP 的本质，即永远复杂的本质，我们确实会找到它，即它最外层的复杂本质。我们还会在这个过程中剥离它的简单性，以确保我们在爬上梯子后扔掉梯子。但是，如果我们寻找方法来调和这两种观点，将 P 和 NP 合并在一起，作为整体理解的简单部分，在这个整体理解中，一个问题的存在需要一个明确的解决方案，那么我们就可以理解，只要有足够的努力和奉献精神，最终就能找到解决方案。无论这个解决方案多么难以捉摸，总有潜力以最流畅和最切实的方式实现它。 现在，为了消除文字上的困惑，我想说我主张 P 最终等于 NP。这只是因为如果我们没有找到解决方案，并不意味着它就不存在，等待我们偶然发现。如果你说我乐观，我想说我认为自己是现实的。 也许我在文章结束前就写了结论。但我喜欢这种风格。它带来了一种“生活”的感觉，我并不是在不断地构建想法，而是一直希望自己能够如此清晰地表达自己，直到文章结束。 科学论文的本质是，你首先要提出你的摘要，例如“P 等于 NP，因为简单性和复杂性是相互交织的”，然后你继续表达你的观点和想法，说明为什么以及如何做到这一点。 然而，在文章中，目标是让读者理解一些东西；这类似于教学。而科学研究的目的是让已经了解该主题的人就所提出的“推理”发表他们的想法和意见，如果有人掌握了一些可以将所有这些观点联系在一起甚至更多的知识，那么这种“推理”就会被重新构建，在逻辑上得到完善，在科学上得到扎根，并成为一种“发现”。 想象一下将两种风格融合在一起。结果会怎样？这就像思想的逐渐成长，一个又一个的洞察力不断涌现。从这个意义上说，摘要将失去意义，因为甚至作者都不知道这条路会通向何方。从这个意义上说，作者可能有一个模糊的想法或一个自我强加的起点，比如证明 P 等于 NP 或 P 不同于 NP。后来，在这种洞察力的构建过程中，一个小小的疏忽可能会指向一个完全不同的方向，然后，试图在不删除最后一个论点的情况下后退只会导致混乱。 就像在有意将第 3 部分重新构建为结论之前，我回到最初的构想，我认为将结论放进去很美。但我怎么才能回到那里呢？我的意思是，作为读者，你可能已经构建了一个又一个想法，并试图掌握一个整体的形式或形状。但这就是它的美妙之处，不是吗？我们可以暂停逻辑推理，让创造力发挥我们的潜力，然后重新开始，焕然一新，用新的视角和更有效的方式得出答案。从这个意义上说，第 3 部分只是暂时的休息。我现在要再休息一下，只是去散散步。之后，我们将讨论第 4 部分。 第 4 部分：分形内部 当我们思考分形时，我们会想象一种自重复的模式，这种模式在所有尺度和维度上都具有相同的属性。例如，曼德布洛特集是一种代表类似于细胞的分形，当你放大该细胞时，你会发现类似的结构一次又一次出现。其实，那些完全相似的细胞状结构并不像你想象的那么常见。最终，分形是如此壮丽，当你将图像放大到一定程度时，你可以非常清晰地看到构成该细胞的每个细节。 它有一部分类似于草叶，其他部分类似于光线穿过黑洞后方时看到的光曲率，还有很多其他有趣的方面。当你将图像放大到一定程度时，你最终会得到相同的初始细胞，相对于起始细胞，它在原子尺度上重复出现。你可以从那里进一步放大。 因此，从本质上讲，分形类似于简单 P 问题中的一条路径，从其所有潜在复杂性来看，它是一个非常令人费解的 NP 问题，似乎无法解决，仅仅是因为解决它需要大量的计算能力（即使解决它的路径是线性的）。例如，您可以将“以 3000 倍缩放绘制 Mandlebort 集”变成一个 P 问题，解决方案是线性的。程序只需遍历分形空间，逐一收集数据，然后将其复制到另一张纸上。但完成完整绘图所需的时间可能非常长。也许，除非我们为程序提供足够的内存和效率来记住所有内容，然后以相同或更高的效率粘贴它。 那么，像“将曼德尔布洛特集完整地复制到这张纸上”这样的问题会被视为 NP 问题吗？毕竟，由于我们可以实现无限的缩放，传递第一个像素需要花费无限的时间，不是吗？但是，如果分形之下有无限的复杂性需要绘制，我们如何在任何尺度上看到分形？也许绘制分形的算法会创建第一幅图像，然后继续无限地努力实现越来越高的复杂性和深度。这让你不禁想问：如果我们从某个半无限的深度（或复杂性）中找到一个不同的图形会怎么样？或者，也许我们会传递一个点，从这个点开始，曼德尔布洛特分形开始以其他方式（也许是相反的方式）表示。 面对这些令人费解的问题，我们确实觉得需要休息一下。就好像我们的大脑因为试图处理这些尺度而超负荷了一样。但是，我们在这里并不是在进行科学研究；我们的目标只是探索这一切的复杂性和巨大性，而不是处理它。也许一旦你形成了相对权重或找到了可以用来理解事物尺度的不同类型的无穷大，事情就会变得更容易。 例如，如果我假设在无穷远处，曼德布洛特集被看作镜像，那么镜像效果可能从半无穷远（或深度）开始发生，这是有道理的。但是，半无穷远并不是真实的。真正意义上的无穷远表明，曼德布洛特集包含曾经存在、可能存在和将永远存在的每种状态、形状和形式。但是，有边界，不是吗？很明显，这种分形只是一种模式。是的，这种模式可能有很多种形状，但仍将受自身、自身结构和规则的约束。无论如何，这种“只是一种模式”本身就非常美丽和复杂。 第五部分：复杂性 正如我之前所说，在构建思想的过程中，我们可能会到达一个点，在这个点上，我们很容易得出与我们的初始假设相反的结论。我的意思是，在复杂性激增之后，人们怎么能相信 P 等于 NP，NP 问题根本不存在呢？但正如我在上一篇文章中所说，当我们表达思想时，我们只是“指向”某个概念。作为一个必需的构建块，分形中发现的复杂性的巨大性必须作为复杂性的潜在“顶峰”提供。当涉及到定义三维无限性到底是什么样子时，理解的顶峰。现在我们周围有这么多无限性，我们能去哪里呢？ 当我们想思考时，我们总是会想到这一点。我们选取一个经典点，观察分形的第一次迭代。所有三维无限性都摆在我们面前。我们推断，如果我们想扔一根针，看看它落在哪里，我们可能会面临一个相当奇怪的现象。针尖越小，它落下所需的时间就越长，地面空间就越大。同时，击中的地面点就会变得越“混乱”或“难以预测”。但是，如果有足够多的无限小的针，我们能否实现分形的整个图像？无论需要多少空间和针？毕竟，从这个有利位置，我们可以清楚地看到极限，除非存在完美的自相似性，否则每次迭代后都必须发生一些损失。 但是，复杂性远远超出了这张地图。说到针头的大小，对于每种尺寸，我们都有一张独特的地图。但是，小针头地图难道不是大针头地图更复杂（和更高质量）的表示吗？从这个意义上讲，复杂性代表了一种更详细空间的展开。一个包含多项式探索路径的空间，甚至与所相信的假设相反，这种复杂性的扩展比缺乏复杂性更能实现更准确、更有效的探索。 例如，如果我们不是使用完全无限复杂的分形图，而是使用一个不太复杂的图，并且想要实现位于更复杂图上的某个地面点，那么我们必须首先在不太复杂的图上选择一个点，然后将其放大并显示我们想要实现的更复杂的点。这个概念颠覆了整个 NP 空间，同时也承认解决特定问题所需的多项式时间可能需要数千年，而且是在多项式路径上。老实说，也许下一个问题是量子计算是否可以拥有一种叠加性，能够将时间从 x 缩短到 x 除以（使用的量子比特数）。 第六部分：结论和想法 在深入探讨量子方法的可能含义之前，我认为有必要先展示一下我迄今为止提出的主张。 P 和 NP 是同一个问题，这意味着一旦我们找到正确的问题空间和正确的解决方案空间，所有问题最终都可以在多项式时间内得到解决 NP 问题更像是广泛多项式问题，其解空间非常庞大且复杂，因此寻找解决方案需要很长时间 复杂性和简单性交织在一起，在它们的相互作用中，我们的视角和所达到的深度水平决定了它们的区别。 我们实现的复杂工具用于更有效地解决详细的问题空间，利用相互作用 在简单与复杂之间寻找优势 归根结底，当我们进入量子计算领域时，事情可能会发生根本性的变化。以下是一些可能的探索途径。 尽管这里说了这么多，但量子计算可能存在自己独特的 NP 问题，这些问题本质上不同于传统计算所提供的问题 量子计算的本质可以同时成为经典计算的一个互补和交织的方面，最终提供量子 NP 问题需要多项式求解的工具 这些量子工具可以与经典算法协同工作，以提供更高的效率，有望绕过两种范式的最大效率 当前的量子计算算法（我不知道它们是如何构建的）可能需要经典计算方面作为功能的先决条件。在这种情况下，我们需要将经典和量子视角归类为两种不同的计算类型，以便能够更好地理解和融合它们 第七部分：量子屏障 鉴于量子力量中蕴藏的巨大潜力，保护我们隐私的系统正面临持续的威胁。ZKP（零知识证明）系统提供了一种可能可行的逃生路线。毕竟，它们的基础是建立在这样的假设之上：钥匙持有者在解锁过程中不会提供任何有关钥匙的信息。从这个角度来看，钥匙就藏在显眼的地方，就在那些想要干扰和窃取钥匙的人的眼皮底下。但与此同时，系统建立和运行的基础能够将整个系统隐藏在外人的视线之外。 这就像是走在计算空间中不断变化且模糊不清的迷宫中，无论是使用经典计算机、量子计算机还是量子经典计算机，你看到的都是一个不断变化的空间，如果你想理解它，你就必须掌握它创建的第一个实例的信息。这样才能访问自系统创建以来启动和塑造系统的构建块。 而在模糊性和系统的海洋中，即使你可以接触到特定系统的构建模块，你也永远不知道将其应用于哪个系统，因为互联系统的海洋太大了，而且有太多的系统会自我交换，在特定的时间间隔内形成彼此的形状。 对于系统本身来说，很容易知道它们应该接受哪些信息，哪些不应该接受，但同时，为了使每个系统都拥有自己独特的视角，需要极端的同步性。然而，考虑到颜色渐变的无限性，每个构建块都可以有自己的起点和持续的目标，这些目标可以限制它们达到另一个系统的颜色状态。你可以想象它类似于无线电波的运作方式。 也许，这种系统中的混乱元素可能会产生一种内部有序的系统，从整体上看，这种系统根本毫无意义。为了破译它，你必须猜测由密码构成的构建块，这些构建块包含数百或数千个在自身范围内不断变化的数字。 从这个角度看，系统越多，攻击者进入系统的机会就越少，但与此同时，系统越多，攻击者的选择就越多。也许量子计算可以让人们一次性在所有可用系统上测试单个密钥。不断生成密钥并同时在整个系统上测试它们。 但是一旦找到当前密钥，就需要“第一个”密钥才能真正进入系统。或者更好的是，通过在系统中存储前 10 个密钥，一旦猜出实际状态密钥，就可以从这 10 个密钥中随机选择一个密钥作为进入的要求。 第 8 部分：层中层，层中层 或者谜题中的谜题。有一件事是肯定的：外部复杂性会蓬勃发展，同时以多项式速度在所有层面上扩展。但是，系统本身必须从某个时刻开始变得如此先进和混乱，以至于即使是先进的外星解密系统也无法利用它，对吗？ 当我们审视现在的处境，将这种复杂性的完全爆发视为一场大爆炸，或者更正式地说，一个奇点时，我们也承认，这些进步只是未来一切的第一步。我们处在一个比以往任何时候都更重视未来的地方，思考未来实际上有助于让未来更加光明。是的，它一直都很重要。但现在，它比以往任何时候都更重要，未来几个世纪也是如此。甚至千禧一代也是如此。 谁知道我们会发现什么？但有一件事是肯定的：我们现在做出的决定将以后代甚至没有选择的方式引导未来。所以我们最好留意他们的观点。在不久的过去（甚至是现在），人们被不情愿地送上战争。人们被迫制造毁灭性武器，甚至试验它们。 但是，如果我们只是理论化武器，而不是制造防御武器所需的盾牌，情况会怎样？为什么要浪费时间试图摧毁我们还没有建造的东西呢？再说一次，当我说宇宙最终可能本质上是善良的时候，你可能会说我乐观。但毕竟，宇宙并没有给我们提供其他的战斗，而是为饥饿而战，这最终让我们感受到每一口食物的美丽和味道。当涉及到知识时，尤其如此。 在我看来，认为超强激光或小型激光阵列更能保护我们的星球免受陨石撞击的想法是愚蠢的，而实际上，只要我们触及表面的一小部分，我们就能找到利用量子引力效应的力量，将其作为一种推进力，类似于炸弹，但这种力量只会反重力扩散。或者，我们可以专注于一种足够强大的火箭，利用极端力量从后面将陨石推离轨道。同时，我们可以用火箭将整列火车运到月球上。 最终，这难道不是解决方案空间的魔力吗？我们可以从有限的视角看待它，假设有些事情我们可能永远不知道，或者我们可以承认自由意志的力量及其塑造整个命运和心灵的真正潜力。