logoalt Hacker News

shoo • today at 1:35 AM • 0 replies • view on HN

Yep! Or for a slightly generalised example, if we pick our sublinear function of n to be n^(1-epsilon) for some small epsilon > 0

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)