UP is much harder to deal with for a very simple reason. Composition of polynomials is still polynomial. Composition of polynomials of low degree leads to polyn

UP is much harder to deal with for a very simple reason. Composition of polynomials is still polynomial. Composition of polynomials of low degree leads to polynomials with high degree. You keep assuming we only look at UP, whereas actually our theoretical work explicitly looks at P. Often, we don't even care about actual efficiency of the algorithm. The constants might be astronomical, but we still like the algorithm for its asymptotic properties. I'm not versed in recent research, but I imagine the composition argument above often leads to polynomial performance with stupid degrees. I expect people only compute the actual degree when they thing it might be low. Again though, this is not my field of research.