Compressing a video looks like a huge decision tree to me, and newer standards add more interdependencies and more variables at each stage. I'd expect that the

Compressing a video looks like a huge decision tree to me, and newer standards add more interdependencies and more variables at each stage. I'd expect that the resulting optimization problems approximated by encoders are computationally difficult. (Which would explain why they always get better even after many years)