And any computable approximation to it looks to me like brute-forcing an NP-hard problem.

I find this a curious thing to say. Isn't this an argument against every possible remotely optimal computable form of induction or decision-making? Of course a good computable approximation may wind up spending lots of resources solving a problem if that problem is important enough, this is not a blackmark against it. Problems in the real world can be hard, so dealing with them may not be easy!

"Omega flies up to you and hands you a box containing the Secrets of Immortality; the box is opened by the solution to an NP problem inscribed on it." Is the optimal solution really to not even try the problem - because then you're trying "brute-forcing an NP-hard problem"! - even if it turns out to be one of the majority of easily-solved problems? "You start a business and discover one of your problems is NP-hard. You immediately declare bankruptcy because your optimal induction optimally infers that the problem cannot be solved and this most optimally limits your losses."

And why NP-hard, exactly? You know there are a ton of harder complexity classes in the complexity zoo, right?

The right answer is simply to point out that the worst case of the optimal algorithm is going to be the worst case of all possible problems presented, and this is exactly what we would expect since there is no magic fairy dust which will collapse all problems to constant-time solutions.