My steps:
Since for two polynomial expressions to be equal, their degrees have to be equal, I decided to compare the degrees of the RHS and LHS. I figured out that the degree of $P(P(x))$ is ${deg(P(x))}^{deg(P(x))}$ And the degree of the LHS can only be 15, $5 \cdot deg(P(x))$ or $deg(Q(x))$. However, I wasn't able to produce a solution from here. Any help would be appreciated.
Best Answer
Let $P(x)= ax^n+...$ and $Q(x) =bx^m+...$ where $a,b>0$. Then $$a(ax^n+...)^n+... = a^5x^{5n} +...x^{15} +bx^m+...$$ so $n^2 = \max\{5n,15,m\}\geq 5n\implies n\geq 5$. If $n\geq 6$ then $n^2 > 5n>15$ so $n^2 =\max \{5n,15,m\} =m $ and thus $m\geq 36$.
So let $n=5$, then $P(x)= ax^5+cx^4+dx^3+...$ and $m\leq 25$.
$$Q(x) = a(ax^5+...)^5 -(a^5x^{25}+...)-x^{15}$$
If $a\neq 1$ then $m= 25$.
If $a=1$ then $$Q(x) = cP(x)^4+...-x^{15}$$ If $c\neq 0$ then degree of RHS is 20 so we put $c=0$, then the degree of RHS is $15$ or less. So let $c=0$ Now we have $$Q(x) = dP(x)^3+...-x^{15}$$ If $d=0 $ then RHS has degree 15 and negative leading coefficient, so $d\neq 0$. If we put $d=1$ we get $$Q(x) = P(x)^3+...-x^{15}$$ and now RHS has degree $<15$.
So if we set $P(x) = x^5+x^3$ we get $Q(x) =3x^{13} + 3x^{11}+x^9 $, so $m_{\min} =13$.