Many inapproximability factors are $2^{n^\epsilon}$. I don't know why this is 2 instead of 3, 4, ..., etc. To be precise, given a problem,theorem 1 says: It's NP-hard to approximate the problem to $2^{n^\epsilon}$ for any $0 \leq \epsilon < 1$;theorem 2 says: It's NP-hard to approximate the problem to $3^{n^\delta}$ for any $0 \leq \delta < 1$.Can we say theorem 2 is tighter?I know that given $\delta < 1$, we can find $\epsilon < 1$ such that $3^{n^\delta} \in \mathcal O(2^{n^\epsilon})$. However, the definition of approximation factor is not in asymptotics. We should get $3^{n^\delta} \leq 2^{n^\epsilon}$ if we want to say the two theorems are actually same.
Why is the inapproximability $2^{n^\epsilon}$?
complexity theory;asymptotics;np hard;approximation
The two theorems are equivalent. You can write$$3^{n^\delta} = 2^{\log_2 3 \cdot n^\delta} = 2^{n^{\delta + \frac{\log \log_2 3}{\log n}}} = 2^{n^{\delta + o(1)}}.$$In particular, for any $\delta' > \delta$ there exists $N$ such that $3^{n^\delta} \leq 2^{n^{\delta'}}$ for all $n \geq N$. Conversely, $3^{n^\delta} \geq 2^{n^\delta}$.Hardness of approximation results are only about large enough $n$. Every problem can be solved exactly in polynomial time (even constant time) for all inputs of size at most $N$, for any fixed $N$.