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

Question

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

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

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

Answer 1

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

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

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

想象一下我们确实编写了代码。要查看所声明的界限是否实际适用，我们可以尝试在一些输入上运行它并绘制运行时图，但这不会告诉我们任何信息。我们的输入可能“不够大”，无法应用渐近上限。如果我们确实得到了一个大的输入，并且我们看到了许多不同输入的运行时间，我们仍然不知道我们是否有最坏情况的运行时间，除非我们尝试了所有可能的输入，但是图的可能输入的数量同构算法作为输入大小的函数呈指数增长。这意味着我们无法暴力尝试所有可能的大尺寸输入，因此我们永远无法确定是否找到了实际的最坏情况输入。有许多算法，如线性规划的单纯形算法，众所周知，除了极少数病理情况外，它们的速度非常快，因此我们总是冒着运行时间与预期不符的风险。

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

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

这就是为什么很难分析此类算法的原因。据我们所知，我们已经拥有图同构的多项式时间算法，但没有人能够证明它具有正确的运行时间。没有多少经验数据可以作为证明，尽管它可能会促使人们尝试证明特定方法运行速度快，作为从理论上证明观察到的运行时间合理的一种方式。