指数中的小O

Question

3^{o(n)} = 2^{o(n)} 吗？

证明 CLIQUE 问题不存在 f(k)n^{o(k)} 时间算法

通过减少三色问题，

有一个说法是 f(k)(3^{n/k})^{o(k)} = 2^{o(k)}。

我想知道如何显示它。

有正式或非正式的证明吗？

Answer 1

是的。 2^o(n) 表示次指数时间。考虑一个更简单的比较：2^o(n) vs 4^o(n):

4^o(n) = (2²)^o(n) = 2^2o(n) = 2^o(2n) = 2^o(n).

这就是直觉。我确信您可以找到更严格的证明，但您可以考虑 cs.stackexchange.com 或数学 stackexchange 之一，因为它们更适合这种严格程度。