I would question whether that holds in the practical LLM automation space.
Can you think of any real life examples where an LLM is likely to be used?
I think in practice what you're saying is there are problems where there exist efficient deterministic verification methods, and I'm sure that's true.
But that's not the bulk of everyday work LLMs are being asked to do nowadays across industry.
You're questioning whether there are any interesting problems in the P v NP space? https://en.wikipedia.org/wiki/P_versus_NP_problem
But if you want to keep it in the realm of the everyday: you're asking if it is easier to write an email than to read it and check it covers what you wanted to say? Is it easier to search for something or to look at what's been found and say that it's what you were looking for?