Also gives the ability to do stuff like "what actions can I take which, within N inferential steps of this model, will produce an outcome I desire?" or "will produce utility > U with probability > P" or such.
Yes, but if the models aren't well-defined then that won't be doable. At this point we can even give rigorous notions what we mean by an intelligence, so our 3-SAT oracle won't be able to help much. The 3-SAT oracle is only going to help for precisely defined questions.
Huh? I'm not sure I understand what your objection.
An NP oracle would let you do stuff like "given this sensory data, find a model of size N or less that within K computational steps or less will reproduce the data to within error x, given such a model exists"
Then one can run "which sequence of actions, given this model, will, within S steps, produce outcome A with probability P?"
Whether or not we can give a rigorous definition of intelligence, seems like the above is sufficient to act like an intelligence, right? Yeah, there're a few t...
Many experts suspect that there is no polynomial-time solution to the so-called NP-complete problems, though no-one has yet been able to rigorously prove this and there remains the possibility that a polynomial-time algorithm will one day emerge. However unlikely this is, today I would like to invite LW to play a game I played with with some colleagues called what-would-you-do-with-a-polynomial-time-solution-to-3SAT? 3SAT is, of course, one of the most famous of the NP-complete problems and a solution to 3SAT would also constitute a solution to *all* the problems in NP. This includes lots of fun planning problems (e.g. travelling salesman) as well as the problem of performing exact inference in (general) Bayesian networks. What's the most fun you could have?