patternMinor
Why is the inapproximability $2^{n^\epsilon}$?
Viewed 0 times
inapproximabilitywhytheepsilon
Problem
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.
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.
Solution
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$.
$$
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$.
Context
StackExchange Computer Science Q#80044, answer score: 4
Revisions (0)
No revisions yet.