When can a polynomial be written as a polynomial function of another polynomial? asks whether, given $p$ and $q$ polynomials, there is a polynomial $w$ with $$ p(x) = w(q(x)) $$ which is a good question with a nice answer. We can try to generalize to ask:
Given a polynomial $p$, do there exist polynomials $q$ and $w$ with $$ p(x) = w(q(x)). $$
That is to say, we can ask the question not for a specific $q$, but ask whether any such $q$ exists.
Alas, that question isn't interesting, for $q(x) = x$ and $w = p$ provides a solution for any $p$; indeed, we can let $q$ be any linear polynomial $q(x) = ax + b$ with $a \ne 0$ and then find $w$ (assuming we're working over a field, which is the case I'm thinking of), essentially by substitution. So my question is this:
Given a polynomial $p$ over a field, is there a (relatively easy) way to determine whether there's a non-linear polynomial $q$ and some polynomial $w$ with the property that $$p(x) = w(q(x))?$$
I'd be happy with an answer even over some specific field like $\Bbb R$ or $\Bbb C$.
@MartinR points out that math.stackexchange.com/a/672847/42969 answers my question quite well (with a solution developed by someone who was a high-school student at the time!)
@BillDubuque points out that computer algebra systems have algorithms to do this kind of thing as well, like this.