上交大校友独作 50年零进展的算法难题被突破

2023-07-03 18:37:11 编辑：崔姬悦来源：

导读近日，芝加哥伊利诺伊大学厄巴纳香槟分校的一名华人科学家提出了一种新的方法，可以通过这种方法更快速的确定群同构，这个问题长达半个世纪...

近日，芝加哥伊利诺伊大学厄巴纳香槟分校的一名华人科学家提出了一种新的方法，可以通过这种方法更快速的确定群同构，这个问题长达半个世纪都没有任何进展，如今已经迎来了新的突破，同构问题的解空间通常是比较庞大的，随着团构规模的增加需要考虑的可能性也会翻倍提升，另一方面来看即便在某个情况下两个结构同构，但是他们两个呈现出来的表现形式也会有所区别，对整体的判断也会造成更多的困难。

在2015年，来自芝加哥大学的学者就已经突破了图同构的加速计算，但是对群同构算法的加速一直都没有取得太好的进展，同构按照定义来说，就是将两个数学结构之间是存在一种相互对应的映射关系，他们包含的各种元素也会处于相同的关系中，比如有两个图形看起来不同，但是他们实际是同构的，因为他们的顶点和边是属于相同的位置，而且点和边之间的关系也是属于同样的。

这个关系可以说是数学理念中的一个重要概念，也是计算机科学的基础之一，在目前广的各个领域都有非常广泛的应用空间，比如使用图同构算法以去监测网络中的一些恶意攻击，也能够分析社交网络的结构关系，使用群同构算法，可以在密码学，数学分析以及图像处理方面取得更重要的作用，在实际运用场景中，不仅需要去确定两个对象是否会是同构现象，也需要去保障整体的计算速度。

这位华人科学家所提出的构思，主要是将群转换成了矩阵，将群同构的问题转化成矩阵是否是相似的问题，在这个问题中，处理的矩阵具有一些特殊性质，任意两个矩阵组合就会演变成另外一个矩阵，这样一来，就会将问题转化成判断两个矩阵空间是否等距的问题，在这个问题探讨的过程中，还引入了一些独创性的内容，从而提高了所有群同构算法的加速可能。

标签：上交大校友，50年零进展的算法难题被突破