5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.