Comment Comment by shoo Yep! Or for a slightly generalised example, if we pick our sublinear function of n to be n^(1-epsilon) for some small epsilon > 0then 2^(n^(1-epsilon)) belongs to 2^o(n)Suppose p(n) is some polyonomial in n, our polynomial reduction. Let's make it a monomial for simplicity, p(n) = n^aDoes 2^(p(n)^(1-epsilon)) necessary belong to 2^o(n)?No, that only holds if (n^a)^(1-epsilon) = n^(a (1-epsilon) ) < n^1 . So, it fails for p(n) = n^a for any a such that a >= 1/(1-epsilon) parent shoo 4 days ago
then 2^(n^(1-epsilon)) belongs to 2^o(n)
Suppose p(n) is some polyonomial in n, our polynomial reduction. Let's make it a monomial for simplicity, p(n) = n^a
Does 2^(p(n)^(1-epsilon)) necessary belong to 2^o(n)?
No, that only holds if (n^a)^(1-epsilon) = n^(a (1-epsilon) ) < n^1 . So, it fails for p(n) = n^a for any a such that a >= 1/(1-epsilon)