They go above and beyond to express how generous they are being when setting the bounds, and sure that's true in many ways, but the requirement that the AI trainer succeeds with non-negligible probability on any set of behaviors is not a reasonable requirement.
If I make a training data set based around sorting integers into two categories, and the sorting is based on encrypting them with a secret key, of course that's not something you can solve in polynomial time. But this paper would say "it's a behavior set, so we expect a tractable AI trainer to figure it out".
The model is broken, so the conclusion is useless.
If it's not solvable in polynomial time, how did nature solve it in a couple of million years?