Definition of Closed Under Left Polynomial Composition
I am studying Computation complexity using <PERSON>'s book: "Computational Complexity". While doing Problem 7.4.4, I came across the definition of what it means for a class of functions $C$ to be closed under left polynomial composition.
Here is 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).
My doubt is what is the correct way of interpreting this definition and proving that a given class of functions $C$ is closed under left polynomial composition. The definition got me confused since the part "for all polynomials $p(n)$" appeared after the part "for some $g(n) \in C$". 603
I thought about two interpretations.
1. Given arbitrary $f(n) \in C$ and $p(n)$, exhibit some $g(n) \in C$ such that $p(f(n)) = O(g(n))$. Then, you have proved that $C$ is closed under left polynomial composition. I think this makes more sense, since by this definition I was able to prove that the class $C = {n^k: k > 0 }$ is "computational model independent", which makes sense to me.
2. Given an arbitrary $f(n) \in C$, exhibit some $g(n) \in C$ such that for all polynomials $p(n)$ we have that $p(f(n)) = O(g(n))$. While assuming this definition, I gave a counterexample and proved that the class $C = {n^k: k > 0 }$ is NOT "computational model independent", which sounds awkward to me.
Which interpretation is the correct one?
Thanks in advance. 945