计算机科学家距离主要算法目标又近了一步广达杂志

如果有人要求您确定两个对象是否相同，这可能看起来是一个微不足道的请求。 在大多数日常情况下，快速浏览一下就足以做出准确的判断。

但在计算机科学中，这是一个更为复杂的问题。 事实上，它切入了计算机能力中尚未解决的核心问题。 根据对象是什么以及如何定义相同性，我们仍然不知道计算机是否可以快速回答问题，或者缓慢而费力的方法是否本质上是它们可以管理的最佳方法。

在过去的十年中，一些重要的结果表明计算机至少可以做得更好一点。 中的一个 最近最大的结果 在计算机科学中，有一种更快的算法来确定两个图何时相同。 2015年工作，由 拉斯洛·巴拜 芝加哥大学的研究人员打破了一个重要的计算速度障碍，但还没有达到另一个目标。

现在，一篇论文 孙晓瑞 芝加哥伊利诺伊大学的教授提出了一种新的、更快的算法来解决称为群同构问题的相关问题，该算法旨在了解称为群的两个数学对象何时相同。 作品发布于网上 刚刚过去的三月，朝着澄清比较对象所涉及的底层计算复杂性迈出了一小步。

孙的工作打破了特定类别群的长期速度限制——该群被认为是群同构问题中最难解决的实例。 如果算法可以快速比较此类组，那么我们希望它可以快速比较任何类型的组。

“我们不知道这样的定理，但我们有理由相信这样的事情应该是正确的，”说 乔什·格罗乔 科罗拉多大学博尔德分校。

比较比较

要精确判断两个事物是否相同，首先需要定义“相同”。 如果两个数字字符串仅包含相同的数字，或者它们可能需要以相同的顺序包含相同的数字，则它们可以被视为相同。

同构是一种特殊的相同性，在数学中经常出现。 当两个对象彼此同构时，大致意味着它们包含相同的元素，并且这些元素彼此之间具有相同的关系。

图——由边（线）连接的顶点（点）的集合——提供了一种易于理解的、直观的方式来了解同构的样子。 如果您可以将一个图中的顶点与另一个图中的顶点进行匹配，使得通过第一个图中的边连接的顶点也通过第二个图中的边连接，则两个图是同构的。 同构图表面上看起来可能不同，但它们共享一个底层结构。

组比图更抽象，但它们仍然可以通过同构进行比较。 组是元素（例如数字）的集合，这些元素可以根据某种操作相互组合，以便结果也在集合中。 例如，您可以有一个组，其元素是整数（所有正整数和负整数，加上零），其运算是加法：将任意两个整数相加，结果始终是另一个整数。

如果您可以将一个组中的每个元素与另一个组中的元素配对，则两个组是同构的，以便对第一组中的两个元素进行操作的结果与对第二组中这些元素的等效值进行操作的结果一致团体。

这是两个组的简单示例，每个组都有两个彼此同构的元素。 第一组由数字 0 和 1 组成，第二组由字母组成 a 和 b。 这两个组都包含以特定方式组合该组元素的操作，其结果列于下表中。

这些群是同构的，因为 0 与 a, 1 对 b，并且通过组合元素产生的结构关系在两组中是相同的。

“如果两个群基本上等价，我们就说它们是同构的，”孙说。

进展不平衡

同构是数学中的一个重要概念——图和群在数学中广泛存在——因为它使数学家能够超越表面的差异，并专注于相关对象实际上可能相同的方式。 但这也是计算机科学的基础。 研究人员不仅寻找确定两个对象是否同构的算法，还测量这些算法的运行速度。

这种测量可能很棘手。 算法的速度取决于其运行时间如何随其处理对象的大小而变化。 例如，假设您有两对组。 在一对中，每组包含五个元素。 在另一组中，每组包含 10 个元素。

您可能希望算法花费更多时间来确定具有更多元素的组是否同构。 但还有多少时间呢？ 会需要两倍的时间吗？ 5² 更长？ 2⁵ 更长？ 这些问题对应于算法速度的重要广泛分类：它们可以在线性时间（这意味着在这种情况下需要两倍的时间）、多项式时间（5² 更长）和指数时间（2⁵ 更长）。

计算机科学家知道大多数计算问题属于哪个速度类别，但不是全部。

“大多数问题要么是最简单的，要么是最难的（这类问题），但仍有一些未知的例外，”孙说。 图和群同构属于例外，这也是它们如此吸引人研究的原因。

在1970s， 罗伯特·塔扬 普林斯顿大学的教授意识到有一种算法可以确定任意两个群是否同构，运行时间为 $latex n^{{(log,n)}}$，其中 n 是每组中的元素数量。 这称为拟多项式时间算法，在运行时层次结构中它比指数时间更好（2ⁿ）但比多项式时间（n²）。 这与 Babai 的图同构算法的速度大致相同，并且在近 50 年后它仍然是我们可以为群做的最好的算法。

“这大致意味着半个世纪以来没有任何进展，”孙说。

在 Tarjan 得出结果时，群同构问题比图版本得到了更广泛的研究。 今天情况发生了逆转，部分原因是图同构激发了令人兴奋的创新，而群同构却停滞不前。

“多年来，我们所有的工具都非常缓慢，并且很难利用我们对[群]代数的了解，”说 詹姆斯·威尔逊 科罗拉多州立大学的。

但是，尽管进展存在差异，这两个问题比它们名称的相似性有更深层次的联系：群同构问题（至少在这个表述中）简化为图同构问题。 这意味着任何可以解决图问题的算法也可以在相似的时间内解决群问题。 反之则不然——小组的进展并不意味着图表的进展。 但群问题缺乏进展，给数学家在图问题上寻求相应进展带来了压力。 如果你不能先完成一些密切相关且看起来更容易的事情，你怎么能完成更难的事情呢？

“也就是说，”孙说，“为了进一步提高图同构，群同构是一个很大的瓶颈。”

问题得到转变

当一个问题的进展像群同构一样长期停滞时，通常需要发明来摆脱困境。 “当你取得重大进展时，这应该表明有一个新想法，”格罗肖说。

Sun 的工作包含一些想法，涉及针对重要类型的群体并找到一种巧妙的方法将这些群体分成几部分以便进行比较。

Sun 算法适用的群体称为 p- 2 类和指数组 p. 它们类似于群，其中两个元素的乘积是另一个元素，并且无论乘法顺序如何，乘积都保持不变。 但真正重要的是它们对整个群同构问题的代表意义。 这些组的结构非常简单，这意味着它们应该很容易进行比较。 但尽管如此简单，研究人员还没有找到加速算法的方法。 在他们能够做到之前，对群同构的一般问题进行改进是没有希望的。

Sun 首先将设置从群切换到矩阵，即作为线性代数基础对象的数字数组。 这之所以成为可能，是因为 1930 世纪 XNUMX 年代的一个称为贝尔对应的定理，该定理将这个版本的群同构问题转化为一个完全类似的矩阵问题。 特别是，Sun 使用矩阵空间，矩阵空间是具有特殊属性的矩阵的集合：空间中任意两个矩阵的（线性）组合等于空间中的另一个矩阵。

换句话说，这些空间的结构很像群体。 因此，Sun 可以尝试理解两个矩阵空间何时是等距的，而不是试图理解两个群何时是同构的——矩阵空间的同构概念对应于群的同构概念。

孙并不是第一个采用这种方法的研究人员，但他是第一个引入额外步骤的人：将矩阵空间分成两部分。 一块是空间的核心，其中所有的矩阵都是简单的。 另一部分是核心周围的空间，其中所有的矩阵都特别复杂。 此移动相当于将一个组拆分为仅包含部分总元素的子组。

然后，Sun 对每个部分应用了不同的算法方法。 核心的结构很简单，因此他使用了结构的表征来以更有条理的方式表示它。 外层更复杂，因此没有明显快速的方法将其与另一层进行比较。 相反，Sun 的方法采用一种称为个体化和细化的方法来排除将一个外层映射到另一外层的大多数可能方式，然后使用计算机来处理所有剩余的可能方式来确定是否存在同构匹配。

该方法在本质上类似于解决数独难题的方法。 有些方块的潜在值受到您已知的（矩阵空间的核心）的限制，因此您可以快速填充它们。 然后还有其他的（外层），它们的约束较少，但你可以通过尝试所有可能的值来找出它们 - 只要这种类型的正方形不是太多，你仍然可以解决这个难题合理的时间。

“我填写了所有我能很快看出是受限制的东西，现在我可能会回去并在丢失的盒子上尝试我的心，”威尔逊说。 “如果你已经缩小了范围，那么现在就是转换方向并使用计算机搜索正确值的好时机。”

Sun 的突破表明，总是可以对对应的矩阵空间进行这种分裂 p- 2 类和指数组 p。 然后他证明，经过这样的分割，算法技术的组合使得可以在 $latex n^{{(log,n)}^{5/6}}$ 时间内确定两个空间是否同构，该值是略低于 Tarjan 的 $latex n^{{(log,n)}}$ 方法。 （这两种算法还包含常数项，这些常数项对运行时没有太大影响，为了清楚起见，我们将其省略。）

结果并不能确定同构属于哪一个速度类别组； 它仍然介于指数时间和多项式时间之间。 但 Sun 已经将其稍微推向了多项式的一面，并且有理由相信比这应该是可能的。 毕竟，他的工作为计算机科学家提供了一种针对最困难的群的更快的群同构算法，从而提高了各种群都可以实现类似加速的可能性。

“如果你能解决这个问题 p-团体，也许你可以解决整个问题，”格罗肖说。 “或许。”