Definition of Closed Under Left Polynomial Composition

Question

I am studying Computation complexity using Papadimitrious'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$". 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.

Answer 1

The correct interpretation is as follows. A class $\mathcal{C}$ is closed under left polynomial composition if the following holds:

For any $f(n) \in \mathcal{C}$ and any polynomial $p(n)$ there exists $g(n) \in \mathcal{C}$ such that $p(f(n)) = O(g(n))$.

In particular, the class $O(n)$ isn't closed under left polynomial composition.

Why are we interested in this definition? Here is an example. We can convert a $k$-tape Turing machine running in time $T(n)$ into a single-tape Turing machine running in time $5kT(n)$, see this question. If we start with a multi-tape Turing machine running in linear time, we don't necessarily end up with a single-tape Turing machine running in linear time. But if we start with a multi-tape Turing machine running in polynomial time, then we do end up with a single-tape Turing machine running in linear time. It thus makes sense that $O(n)$ isn't closed under left polynomial composition, but $n^{O(1)}$ is.