实现Babai拟多项式图同构？

Question

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

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

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

Answer 1

让我们想象一下，您确实实现了该算法。你能用它来验证这个算法的时间复杂度吗？

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

• 对于足够大的投入，
• 从这么大的可能投入中，
• 运行时至多是n的常量倍数。

所以想象一下我们确实对它进行了编码。要查看声称的绑定是否真的适用，我们可以尝试在几个输入上运行它并绘制运行时，但这不会告诉我们任何事情。我们的输入可能“足够大”，不足以应用渐近上限。如果我们确实得到了一个大的输入，并且我们在许多不同的输入上看到了运行时，除非我们尝试了所有可能的输入，否则我们仍然不知道我们是否有最坏的运行时，但是一个图同构算法的可能输入的数量随着输入的大小呈指数增长。这意味着我们不能用蛮力来尝试所有可能的大尺寸输入，所以我们永远无法确定我们是否找到了实际的最坏的输入。有许多算法，比如线性规划的单纯形算法，除了罕见的病理情况外，已知速度非常快，所以我们总是冒着运行时不符合我们预期的风险。

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

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

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

Answer 2

实用图同构在P.参见Brendan的小淘气实现。

nauty和Traces是计算图和有向图的自同构群的程序。他们也能产生一个标准的标签。nauty和Traces是在一个可移植的C子集中编写的，并且运行在相当多的不同系统上。

Babai的结果只是理论上的兴趣。