What would you do with a solution to 3-SAT?
I'll tell you what I'd do, man: two chicks at the same time, man.
Anyway, my actual answer would have been about the same as jimrandomh's, but, assuming I'm the only one who has the polynomial-time solution to 3-SAT, in the absence of sufficiently specific knowledge about how to create an FAI, I would use it to make huge amounts of money (either by using it to get a significant advantage in prediction and using that to play the stock market (etc.) or just by making super-useful thitherto-impossible products or services using it) and then use that to support said universe-optimization efforts.
There's a nice paper about that by Scott Aaronson (pdf)
If such a procedure existed, then we could quickly find the smallest Boolean circuits that output (say) a table of historical stock market data, or the human genome, or the complete works of Shakespeare. It seems entirely conceivable that, by analyzing these circuits, we could make an easy fortune on Wall Street, or retrace evolution, or even generate Shakespeare’s 38th play. For broadly speaking, that which we can compress we can understand, and that which we can understand we can predict.
He...
The perpetual motion machines you refer are only that in a very metaphorical sense -- they don't allow an infinite extraction of some energy-like metric.
Glider guns produce an endless stream of gliders to give the simplest example.
That is a bit poetic. In the Fibonacci case, we know that there is a simple explanation/formula. For the stock market, genome, or Shakespeare, it is not obvious that the smallest circuit will provide any significant understanding. On the other hand, if there's any regularity at all in the stock market, the shortest efficient description will take advantage of this regularity for compression. And, therefore, you could use this automatically discovered regularity for prediction as well.
On the other hand, if several traders get their hands on efficient NP computers at once, it's safe to bet that historical regularities will go out the window.
OBVIOUSLY the answer to this question is:
I would assemble a documentary crew, and make a movie about me visiting the town and city halls of every town and city in America. I would travel the minimum distance possible, and do nothing particularly interesting at any location. I would release my video into the Creative Commons, and open up a website to go with the video. There would be a google map-like toy that invites users to plot their own tour of all the towns and cities in Europe. This will be my way of testing initiates into the Better Bayesian Conspir...
What would you do with a solution to 3-SAT?
Any answer other than "create a superintelligent friendly AI to optimize the universe" would be a waste of this particular genie, but there are some steps in between that and 3-SAT which I can't specify yet.
Do you agree that the FAI problem has to be solved sooner or later?
...And right now, thinking about possible replies to your comment, I finally switched to agreeing with that. Thanks.
Oh hell. This changes a lot. I need to think.
I would settle all famous conjectures in mathematics. Or at least the ones with short enough proofs/refutations.
Daniel's statement:
"Given a statement S of ZFC and a number n, is there a proof of S that is shorter than n?"
Is trivially in NP.
The oracle itself is what gives one the ability to perform this computation: Find compact model that efficiently predicts/explains with bounded error the observed sensory data. (This is rough description of the more precise version stated above)
Also gives one the ability to efficiently perform this computation: Given a generated model, determine actions that will lead to desired outcome in bounded number of steps, with reasonably good probability.
The ability to perform the former computation would amount to the ability to efficiently learn. The ability to perform the latter computation would amount to the ability to efficiently plan.
ie, if one has an algorithm for efficiently solving NP complete problems, one can be really good at doing the above two things. The above two things amount to the ability to learn and the ability to plan.
clearer version: the first type of computation would allow it, from observation and such, to determine stuff like the laws of physics, human psychology, etc...
The second computation would allow it to do stuff like... figure out what actions it needs to take to increase the rate of paperclip production or whatever.
(incidentally A slight amount of additional reflectivity, without needing to solve the really hard problems of reflective decision theory or such, would probably be sufficient to allow it to figure out what experiments it needs to do to gain data it needs to form better models.)
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?