algorithm - 实现八佰的拟多项式图同构？

Question

有没有人实现过 Laszlo Babai 的准多项式图同构？

http://people.cs.uchicago.edu/~laci/

我不是这方面的专家。我想知道 为什么不直接实现他的算法并运行它来验证它的时间复杂度？

Answer 1

让我们假设您确实实现了该算法。你能用它来凭经验验证该算法的时间复杂度吗？

不幸的是，答案是否定的。如果我们说算法的时间复杂度是 O(f(n))，那么我们就是说

• 对于足够大的输入，
• 在该大小的所有可能输入中，
• 运行时间至多是 n 的常数倍。

所以想象一下，我们确实对它进行了编码。要查看声称的界限是否真的适用，我们可以尝试在一些输入上运行它并绘制运行时，但这不会告诉我们任何事情。我们的输入可能不够“大”，无法应用渐近上限。如果我们确实获得了一个大输入并且我们看到了许多不同输入的运行时间，我们仍然不知道我们是否有最坏情况的运行时间，除非我们尝试了所有可能的输入，但是图的可能输入的数量同构算法作为输入大小的函数呈指数增长。这意味着我们无法暴力尝试所有可能的大尺寸输入，因此我们永远无法确定是否找到了实际的最坏情况输入。

还有很多实际问题会出现。算法的理论分析通常不考虑缓存行为、分页、抖动等，因此我们可能会看到某些大型输入需要比预期更长的时间，这仅仅是因为它们不能很好地处理缓存。在这种情况下，即使原始操作数量的分析是正确的，我们也可能会看到运行速度比预期慢得多。

简而言之，在实际输入上运行算法的次数永远不会让您确认或否认运行时分析是正确的。如果它看起来符合趋势，那就太好了......但是你没有尝试查看的所有无限多的输入呢？如果它似乎与预测的趋势不匹配，你怎么知道你只是没有尝试过足够大的输入？或者您在分析中看到来自其他因素的噪音？

这就是为什么很难分析这样的算法。就我们所知，我们已经有了一个用于图同构的多项式时间算法，但是没有人能够证明它具有正确的运行时间。没有多少经验数据可以作为证明，尽管它可能会激励人们尝试证明某种特定方法运行得很快，以此作为从理论上证明观察到的运行时间的一种方式。

Answer 2

实用的图同构在 P 中。参见 Brendan McKay 的nauty的 C 实现。

nauty 和 Traces 是用于计算图和有向图的自同构组的程序。他们还可以产生规范的标签。nauty 和 Traces 是用 C 的可移植子集编写的，可以在相当多的不同系统上运行。

Babai 的结果仅具有理论意义。