求证3^{o(n)}=2^{o(n)}及CLIQUE问题时间复杂度推导合理性

一、$3^{o(n)}$ 是否等于 $2^{o(n)}$？ #

答案是是的，二者在渐近意义下等价，以下是正式证明：

根据小o记号的定义：若函数 $f(n) \in o(n)$，则对任意 $\varepsilon > 0$，存在 $N > 0$，当 $n > N$ 时，$|f(n)| \leq \varepsilon n$。

1. 证明 $3^{o(n)} \subseteq 2^{o(n)}$：
   设 $f(n) \in o(n)$，则 $3^{f(n)} = 2^{f(n) \cdot \log_2 3}$。由于 $\log_2 3$ 是常数，$f(n) \cdot \log_2 3$ 仍满足 $o(n)$ 的定义（对任意 $\varepsilon' > 0$，取 $\varepsilon = \varepsilon' / \log_2 3$，则 $|f(n) \cdot \log_2 3| \leq \varepsilon n \cdot \log_2 3 = \varepsilon' n$），因此 $3^{f(n)} \in 2^{o(n)}$。

2. 证明 $2^{o(n)} \subseteq 3^{o(n)}$：
   同理，设 $g(n) \in o(n)$，则 $2^{g(n)} = 3^{g(n) \cdot \log_3 2}$，$\log_3 2$ 是常数，故 $g(n) \cdot \log_3 2 \in o(n)$，因此 $2^{g(n)} \in 3^{o(n)}$。

综上，$3^{o(n)} = 2^{o(n)}$。

二、归约中等式 $f(k)(3^{n/k}){o(k)} = 2^{o(n)}$ 的推导（注：原表述可能存在笔误，应为 $2^{o(n)}$） #

我们逐步拆解推导过程：

1. 化简指数项：
   首先展开 $(3^{n/k}){o(k)}$，根据指数运算法则：
   $$(3^{n/k}){o(k)} = 3^{(n/k) \cdot o(k)}$$

2. 分析 $(n/k) \cdot o(k)$ 的渐近阶：
   设 $h(k) \in o(k)$，根据小o定义，对任意 $\varepsilon > 0$，存在 $K > 0$，当 $k > K$ 时，$|h(k)| \leq \varepsilon k$。代入得：
   $$|(n/k) \cdot h(k)| \leq (n/k) \cdot \varepsilon k = \varepsilon n$$
   这说明 $(n/k) \cdot h(k) \in o(n)$，因此：
   $$3^{(n/k) \cdot o(k)} = 3^{o(n)}$$

3. 结合第一部分结论替换：
   由 $3^{o(n)} = 2^{o(n)}$，可得：
   $$(3^{n/k}){o(k)} = 2^{o(n)}$$

4. 处理 $f(k)$ 项：
   $f(k)$ 是仅依赖参数 $k$ 的函数，在CLIQUE问题的归约语境中，$f(k)$ 通常是可计算的函数（如多项式或指数级关于 $k$）。当我们考虑 $n \to \infty$ 的渐近分析时：

   • 若 $k$ 固定，$f(k)$ 是常数，可被吸收到 $2^{o(n)}$ 中（因为常数是 $2^{O(1)}$，而 $O(1) \subseteq o(n)$ 当 $n \to \infty$）；
   • 若 $k$ 随 $n$ 增长（如 $k = o(n)$），则 $\log f(k) = o(n)$，故 $f(k) = 2^{o(n)}$，此时 $f(k) \cdot 2^{o(n)} = 2^{o(n)} \cdot 2^{o(n)} = 2^{o(n)}$。

综上，整个表达式最终可化简为 $2^{o(n)}$。

内容的提问来源于stack exchange，提问作者CYALSKII