Deep Dive
Shownotes Transcript
在本集中，Kyle 概述了图论与计算复杂性理论的交集。在复杂性理论中，我们关注的是算法基于其输入大小的运行时间。对于许多图问题，我们想要提出的有趣问题需要越来越长的时间才能解答！本集提供了探索图论与计算复杂性理论交集的路径上的基本词汇和路标。</context> <raw_text>0 您正在收听 Data Skeptic：图与网络播客，该播客探讨了图数据结构如何影响科学、工业以及其他领域。欢迎收听 Data Skeptic：图与网络的另一期节目。正如许多人所知，我们通过算法过程找到绝大多数嘉宾。
我们爬取 Archive 等网站。我们有一个机器学习优先级排序过程。但我自己也进行了一些更传统的搜索，尤其是在我觉得我们的报道可能存在差距时。而我无法仅用合适的嘉宾填补的差距之一是有人来谈论复杂性理论。
具体来说，显然是在图和网络的背景下。因此，对于任何不熟悉复杂性理论的人，我将快速地为您讲解一下。关于算法，您想要提出的主要问题之一是它的扩展性如何。如果我将其输入大小加倍，它是否需要花费两倍的时间？也许更糟，也许是四倍的时间，一百倍的时间。
在少数情况下，例如二分查找，您可以将输入大小加倍，而查找解决方案所需的时间不会增加那么多。它更像是 n 的对数项。因此，我们对图提出的任何问题，我们在网络上运行的任何算法，通常情况下，您都会听到人们遇到可扩展性挑战，特别是图问题。
尽管情况并非总是如此。让我们从一些最快的算法开始我们的旅程：亚线性时间算法。那么亚线性是什么意思呢？在计算复杂性理论中，一切都是渐近线。因此，我们有一个输入大小，我们总是将其称为 n。然而，这在图中有点令人困惑。有时您需要 n 来表示节点，或 v 来表示顶点，e 来表示边，
图确实可以通过两种方式增长。它们可以在节点大小和边数上增长，这将以不同的方式影响某些算法。随着它的增长，您的算法如何执行？好吧，亚线性方法意味着，如果您将输入大小加倍，则不一定会使运行时间加倍。这听起来确实很棒。您可以快速获得有关图的问题答案，但前提是您可以使用亚线性时间算法来表达该问题。
这可能类似于采样。如果您想知道有向图中节点的平均传入边数，是的，您可以进行一些子采样。该总体平均值是多少？也许可以使用自举法，进行几次，并依赖中心极限定理。您将对网络的平均传入链接或入度有一个很好的估计。但您只是依赖统计数据。
如果您关心的是，比如说，最大值，那么唯一确保您获得最大值的方法是查看每个元素。而您采样到最大值的几率相当低。有一些草图和流算法可以为您做一些巧妙的事情。例如，估计网络中三角形的数量。三角形是指三个人互为朋友或互连的情况。我应该说三个节点是互连的。
好吧，在亚线性之后，是线性时间算法。如果您的问题可以用线性时间算法表达或解答，那么您也应该感到幸运。有很多经典且仍然非常有用的算法可以在线性时间内运行。这就是您通常看到的 V + E 或顶点加边的写法。计算节点数，计算边数，这就是您在定义网络大小时的 N。
广度优先搜索和深度优先搜索。两者都是 O(V + E)。拓扑排序、连通分量、循环检测、检查二分性以及我在开始这项研究之前从未听说过的一系列其他内容。您可以有效地回答有关图的所有问题。有人可能会认为这就是为什么 Google 能够使用广度优先搜索扩展到 Web 规模爬取的原因。
或者为什么 Facebook 能够成功地进行一些诸如连通分量分析之类的操作。现在，如果您是一位真正的复杂性理论家，那么我已经跳过了很多细微差别。但如果我们要重点介绍一下，我们会从线性算法到多项式时间算法。那些运行时间为 n 平方、n 立方、n 的 4 次方之类的算法。因此，随着图大小的增加，计算时间会大幅增加。
然而，也许从实际的角度来看，我们可以扩展它并找到一种使其具有成本效益的方法。全对最短路径算法的计算，Floyd-Warshall 算法，如果您正在使用某个拓扑系统或导航系统，那么预先计算所有点之间的距离可能很有用。您可能会在某些优化问题中遇到的最大流算法，
PageRank 和特征向量中心性、图划分和精确的三角形计数，与我之前提出的近似值相反。所有这些以及更多都在最坏情况下以多项式时间完成。在实践中，如果您真的要扩展某些东西，您可能需要一个工程团队和一个新颖的云解决方案。如果您的数据足够小，也许您可以将所有数据都塞进一台机器中，获得一台内存很大的强大机器，
如果您的图特别稀疏，那么并行化过程就很容易。然而，与许多其他大数据挑战不同的是，您很少能够将图分割成这些子图。首先，它可能并不那么稀疏。大多数现实世界的图都是高度连接的，或者即使它们不是，它们仍然具有一个巨大的连通分量，即图中最大的分量，它肯定会包含……
如果您正在处理某些大数据问题，则会有大量的节点。目前尚不清楚我们能否仅仅分割该连通分量并将其推送到无限可并行化的机器上。我们可以通过这种方式近似地进行处理，但即使在规模上，也需要开发一些非显而易见的解决方案，在工业应用中通常需要一些新颖的东西。许多使用图的大型参与者最终会在过程中发明新事物也就不足为奇了。
如果我们对复杂性理论的快速概述从亚线性、线性到多项式时间算法有一个明显的下一个访问点，那就是 NP 完全图问题。这是一类非常特殊的难题，它与计算机科学中最大的开放性问题之一有关：P 与 NP。
在当今数据驱动的世界中，能够从数据中提取价值不仅仅是一种优势，而是必不可少的。掌握分析可以改变您的职业生涯以及您工作的组织。轮到您通过分析来改变您的职业生涯并推动组织取得成功了。让我告诉您佐治亚理工学院谢勒商学院的商业分析研究生证书。
它是 100% 在线课程。谢勒商学院在美国排名前 10 的商学院中为忙碌的商业分析专业人士提供服务。他们拥有一流的教师团队，可以帮助您在短短一年内毕业，但是
但也许您像我一样忙碌，并且想慢一点。您可以将灵活性与严格的教育相结合。谢勒的研究生证书项目适应您的生活，而不是相反。他们的项目是为像我们这样的专业人士设计的，他们希望利用数据并解决现实世界的业务挑战，但需要灵活的时间和安排。
这就是为什么您可以根据自己的情况安排课程。最重要的是，您不仅仅是在获得证书。您还可以打开佐治亚理工学院享有盛誉的 MBA 项目的大门。现在是时候成为佐治亚理工学院商业分析研究生证书的数据精通领导者了。2026 年春季的申请现已开放。
访问 techgradcertificates.com 了解更多信息并在 8 月 1 日截止日期之前申请，网址为 techgradcertificates.com。
构建多智能体软件很难。智能体到智能体和智能体到工具的通信仍然处于蛮荒时代。这显然是新兴的未来，但是您如何在非确定性智能体应用程序中实现准确性和一致性？这就是 Agency 的用武之地。他们的拼写非常巧妙。以下是它的拼写方式。
A-G-N-T-C-Y。我过一会儿再告诉你一次。Agency 是一个构建智能体互联网的开源集体。智能体互联网是一个协作层，AI 智能体可以在其中进行通信、发现彼此并在框架之间工作。对于开发人员来说，这意味着标准化智能体发现工具。
无缝的智能体间通信协议以及用于组合和扩展多智能体工作流的模块化组件。与其他关心高质量多智能体软件的工程师一起构建。看看您可以在这个生态系统中扮演什么角色。访问 agency.org 并添加您的支持。网址是 A-G-N-T-C-Y dot O-R-G。是 NP 完全图问题。
这是一类非常特殊的难题，它与计算机科学中最大的开放性问题之一有关，即 P 与 NP。这很好，但它是什么呢？这是一种特殊的难题，其中找到解决方案似乎非常困难，但验证解决方案似乎很容易。
有很多这样的例子。我认为旅行商问题可能是最流行的，也许在许多讲座和课程中都是首选。这对我来说很好，因为旅行商问题是一个图问题。您有多种目的地。将它们想象成城市、供应商演示等等。这是销售人员与其客户之间的一种物理接触点。不允许使用缩放。
而旅行推销员想要找到一条高效的路线。在某些情况下，这很容易。想象一下，您住在完美的圆形湖泊附近。周围有一条环形路。您唯一真正的争论是您是在巡回演出中顺时针还是逆时针行驶？
如果您只考虑这些简单的例子，很容易说服自己这个问题很容易解决。好吧，它显然是可以解决的。旅行推销员可以找到一条完整的路线。他或她能否找到最有效的路线？这就是挑战。
或者更具体地说，他们能否在平均情况下做到这一点，而不是我们那个只有一个环形路围绕着的昏昏欲睡的湖边小镇？我实际上更喜欢拼图的比喻。当我想到拼图时，我经常会想到它可能有一个蛮力组件。
我可以看到图像的某些部分，我有一些线索，但没有一种算法适用于所有拼图。也许只是蛮力，尝试每种组合的每种耦合，直到你得到它。然而，一旦你得到了它，一旦你组装了拼图，如果你把它展示给某人，他们会很快识别出你是否完成了拼图。所有 NP 完全问题都是如此。我们正式称之为见证字符串。
让我们进入形式化，而不是我松散的定义。因此，NP 完全问题是指其解决方案可以在多项式时间内验证的问题。这非常具体，也许您可以比多项式时间更快地验证某些内容。该问题将具有其他特性，几乎肯定不会使其落入 NP 完全类别。好的，易于验证，或者至少与多项式时间算法一样容易。
但关键的警告是，没有已知的解决方法可以在多项式时间内运行。您可以验证解决方案，但不能可靠地始终在多项式时间内找到解决方案。或者至少这是几乎每个人都相信的。
还没有人证明这一点。这就是这个中心问题 P 与 NP 的关键所在。P 等于 NP 似乎几乎是荒谬的，但到目前为止，我们既缺乏表达这种证明的适当数学方法，也缺乏足够聪明的表达我们已经拥有的数学中解决方案的人。我称这些 NP 完全问题为一类。
如果您去学习它，您将了解它们之间的多项式时间归约，这是我们说两者相等的一种非常正式的方式。我们在这里将跳过这一点，我只是给您列出一些所有都具有此属性的著名图问题。易于验证，难以解决。旅行推销员，就像我们讨论的那样。哈密顿循环。图着色。最稀疏切割问题。最大团。以及子图同构。
我希望我们对这些精彩的话题中的每一个都进行过正式的介绍。让我们只谈谈子图同构。
这就像询问较大的图中是否存在小的模式。所以想象一下一个图，也许是您的社交网络，现在让我们随机但一致地将您认识的所有名称替换为虚构的名称。如果您观看我执行此过程，很容易说我将您的现实世界社交网络一对一地映射到我的虚构角色上。
但是，如果您想提出这样的问题，社交网络上还有其他人与我拥有相同的精确朋友结构吗？现在，如果我只有两个朋友，而我们都在这个小三角形中互为朋友，那么很容易识别出那里还有其他三角形。但在庞大的人际网络中，说我的确切模式，我的本地局域网，是否存在等效的结构？
在更大的图中的某个地方。如果有，如果您给我带来解决方案，我可以很快验证它。只需比较两者即可。但是，我将从哪里开始寻找这样的匹配，我甚至不知道可能存在哪些好的方法。无论它们是什么，我们都知道它们都不能在多项式时间内得到正确的答案。因为如果他们做到了，
我们可以使用相同的解决方案来解决许多其他问题。那么这是否使事情变得毫无希望？当我们遇到 NP 完全问题时，我们是否会放弃？由于有如此多的图算法和方法可以回答 NP 完全类中关于图的问题，这是否意味着图只是无法访问的、过于复杂的物体，不值得我们花费分析时间？好吧，当然不是。
事实是，至少在工业界，您很少需要对精确解的确认。如果您能放宽这一点，NP 完全问题就不会像看起来那样麻烦。好吧，也许我找不到旅行推销员可以遵循的完美路线。但是，如果我可以让这条路线接近最优，达到 99% 的最优呢？
或者更好的是，至少达到 99% 的最优答案。仅仅通过这种轻微的妥协，您就可以使用这种不可否认的较次算法。它不会为您提供精确的解决方案，但如果它可以快速或有效地为您提供 99% 接近的解决方案，那么我们应该能够做些什么。因此，如果有什么不同的话，也许结论是图问题是在工业界追逐的最有趣的问题。
这并不像将它们转储到某些大数据解决方案中并依赖供应商来完成所有有趣的事情那样简单。如果您能理解这些类别，哪些问题确实很难，以及可以部署哪些可行的近似方法，
并且您可以与云工程师和软件工程师合作，或者也承担这些职责。为了提供解决某些现实世界问题的可扩展解决方案，管理图的固有难度使您成为一项关键资产，而大型语言模型（LLM）不太可能很快取代它。或者至少这是我的看法。但是，无论您现在或将来是否有机会处理多大规模的图数据，
您可能必须面临的挑战之一是如何扩展您的分析。如果网络有任何意义，并且可能值得研究，那么它必须有很多节点和边。您可能认为很容易回答的一些问题，例如计算最短路径，或者您组织中的一些喜欢流行语的热门人物认为您应该计算 PageRank 并以某种巧妙的方式使用它。
这些任务说起来容易做起来难。帮助阐明这些挑战的存在以及来自复杂性理论的基本挑战，可以使您成为组织内更好的沟通者，并有望部署基于图的解决方案。