For your second objection by "efficient algorithm", I meant an algorithm that is practically efficient on very large problems. That probably means no worse tha

For your second objection by "efficient algorithm", I meant an algorithm that is practically efficient on very large problems. That probably means no worse than O(N^2), but preferably more like O( N*log(N) ). For your first objection I think a modified form of AIXI probably already solves most of the "non-optimization" challenges of AI. By modified form, I basically mean replace minimum size Turing Machines with minimum size boolean circuits to transform an uncomputable problem into one that is computable and that would be tractable given the scenario we are discussing. In other words you would essentially be doing reinforcement learning by searching for small boolean circuits which maximize the objective function. Of course there is the rather important matter of defining the objective function itself, which P=NP may not directly help much with. I think that with a sufficiently powerful optimization algorithm you will get (super-)intelligent behavior almost no matter what the objective function (as Boscom has argued with his paper-clip scenario). The question would be more whether the intelligent behavior that arises is desirable for humans or not. Even if you don't believe in my AIXI-like approach just look at what a highly suboptimal optimization algorithm like gradient ascent has done when applied to deep neural networks. If you can get superhuman go players and image recognizers with that, what would you get using a universal global optimizer ? Finally we are talking about a scenario where mathematics is basically a solved problem (in the sense that you would have an automatic theorem prover that could prove any theorem you could state formally). If that world wouldn't lead quickly to general AI then there would have to be some mystery to intelligence that is literally deeper than mathematics itself, which is hard for me to believe.