Classes of Functions Closed Under Polynomial Composition - Papadimitriou Exercise 7.4.4

Question

I am studying Computation complexity using Papadimitrious's book: "Computational Complexity".

I am trying to do Problem 7.4.4:

"Let $C$ be a class of functions from nonnegative integers to nonnegative integers. We say that $C$ is closed under left polynomial composition if $f(n) \in C$ implies $p(f(n))=O(g(n))$ for some $g(n) \in C$, for all polynomials $p(n)$. We say that $C$ is closed under right polynomial composition if $f(n) \in C$ implies $f(p(n))=O(g(n))$ for some $g(n) \in C$, for all polynomials $p(n)$.

Intuitively, the first closure property implies that the corresponding complexity class is "computational model-independent", that is, it is robust under reasonable changes in the underlying model of computation (from RAM's to Turing machines, to multistring Turing machines, etc.) while closure under right polynomial composition suggests closure under reductions (see the next chapter)."

Which of the following classes of functions are closed under left polynomial composition, and which under right polynomial composition?

(a) - $\{n^k: k > 0 \}$

(b) - $\{k \cdot n: k > 0 \}$

(c) - $\{k^n : k > 0 \}$

(d) - $\{2^{n^k} : k > 0 \}$

(e) - $\{\log^k n: k > 0 \}$

(f) - $\{\log n\}$

After understanding the definition of closed under left/right polynomial composition, I think I was able to solve items (a), (b), (c) and (f). However, I was not able to solve items (d) and (e).

My solution for item (a):

Closed Under Left Polynomial Composition: consider an arbitrary $f(n) \in C$ and an arbitrary polynomial $p(n)$. Then, $f(n)$ is of the form $n^{k'}$, for some $k' > 0$ and therefore $p(f(n))$ is a polynomial. Let $k''$ be the degree of the polynomial $p(f(n))$. Take $g(n) = n^{k''} \in C$ and we have $p(f(n)) = O(g(n))$.

Closed Under Right Polynomial Composition: same reasoning.

My solution for item (b):

Not Closed Under Left Polynomial Composition: consider as a counterexample $f(n) = n \in C$ and $p(n) = n^2$. Then, $p(f(n)) = n^2$. For every $g(n) = k n \in C$ we have $O(g(n)) = O(n)$. Since $n^2 \neq O(n)$ we conclude.

Not Closed Under Right Polynomial Composition: the previous counterexample applies.

My solution for item (c):

Closed Under Left Polynomial Composition: Consider an arbitrary $f(n) = k_1^n$ and a polynomial $p(n)$. Notice that $p(f(n))$ is a polynomial in $k_1^n$. For sufficiently large $n$, there exists some $k_2$ such that $p(n) \leq n^{k_2}$ and therefore $p(f(n)) \leq [f(n)]^{k_2} = (k_1^{n})^{k_2} = (k_1^{k_2})^n$. Therefore, taking $g(n) = (k_1^{k_2})^n \in C$ we obtain that $p(f(n)) = O(g(n))$.

Not Closed Under Right Polynomial Composition: Consider as a counterexample $f(n) = 2^n$ and $p(n) = n^2$. Then, $f(p(n)) = 2^{n^2}$, which is greater than $g(n) = k^n$, for every fixed value of $k$, if $n$ is sufficiently large. Therefore, $f(p(n)) \not \in O(g(n))$.

My solution for (f):

Not Closed Under Left Polynomial Composition: Consider as a counterexample $f(n) = \log n$ and $p(n) = n^2$. Then, $p(f(n)) = \log^2 n$. Also, $g(n) \in C$ implies that $g(n) = O(\log n)$. We have $\log^2 n \not \in O(\log n)$.

Closed Under Right Polynomial Composition: If $f(n) \in C$ then $f(n) = \log n$. Given an arbitrary polynomial $p(n)$, we have that there exists some $k'$ such that, for sufficiently large $n$, $p(n) < n^{k'}$. Then, for sufficiently large $n$: $ f(p(n)) \leq f(n^{k'}) = \log n^{k'} = k' \log n = O(\log n) = O(g(n)).$

Can anyone help me with items (d) and (e)?

Thanks in advance. Of course, corrections/comments on the other items are also welcomed.

Answer 1

For item (d):

Closed under left polynomial composition: Consider an arbitrary $f(n) = 2^{n^{k_1}} \in C$ and an arbitrary polynomial $p(n)$. There exists some $k_2$ such that $p(n) \leq n^{k_2}$, for sufficiently large $n$. For sufficiently large $n$, $p(f(n)) \leq [f(n)]^{k_2} = [2^{n^{k_1}}]^{k_2} = 2^{k_2 n^{k_1}}$. There exists $k_3$ such that $2^{k_2 n^{k_1}} < 2^{n^{k_3}}$ for sufficiently large $n$. Therefore, choosing $g(n) = 2^{n^{k_3}} \in C$ we have $p(f(n)) = O(g(n))$.

Closed under right polynomial composition: Consider an arbitrary $f(n) = 2^{n^{k_1}} \in C$ and an arbitrary polynomial $p(n)$. There exists some $k_2$ such that $p(n) \leq n^{k_2}$, for sufficiently large $n$. For sufficiently large $n$, $f(p(n)) = 2^{[p(n)]^{k_1}} \leq 2^{(n^{k_2})^{k_1}} = 2^{(n^{k_2 k_1})}$. Therefore, taking $g(n) = 2^{(n^{k_2 k_1})} \in C$ we obtain that $f(p(n)) = O(g(n))$.

For item (e):

Closed under left polynomial composition: Consider an arbitrary $f(n) = \log^{k_1} n$ and an arbitrary polynomial $p(n)$. Then, exists some $k_2$ such that $p(n) \leq n^{k_2}$, for sufficiently large $n$. Therefore, for sufficiently large $n$, $p(f(n)) \leq f(n)^{k_2} = (\log^{k_1} n)^{k_2} = \log^{k_1 k_2} n$. Choosing $g(n) = \log^{k_1 k_2} n$ we have $p(f(n)) = O(g(n))$.

Closed under right polynomial composition: Consider an arbitrary $f(n) = \log^{k_1} n$ and an arbitrary polynomial $p(n)$. Then, exists some $k_2$ such that $p(n) \leq n^{k_2}$, for sufficiently large $n$. Take $g(n) = \log^{k_1} n$. We have, for sufficiently large $n$: $ f(p(n)) = \log^{k_1} p(n) \leq \log^{k_1} (n^{k_2}) = (k_2 \log n)^{k_1} = {k_2}^{k_1} \log n^{k_1} = O(\log n^{k_1}) = O(g(n))$.