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.
I don’t see how a circuit overfitted to any of the above would help you.
That’s just the thing, the smallest circuit wouldn’t be over-fitted. For instance, if I gave you numbers 1,1,2,3,5,8,13,21… plus a hundred more and asked for the SMALLEST circuit that outputted these numbers, it would not be a circuit of size hundred of bits. The size would be a few bits, and it would be the formula for generating the Fibonacci numbers. Except, instead of doing any thinking to figure this out, you would just use your NP machine to figure it out. And essentially all mathematical theorems would be proved in the same way.
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.
I don’t see how a circuit overfitted to any of the above would help you.
That’s just the thing, the smallest circuit wouldn’t be over-fitted. For instance, if I gave you numbers 1,1,2,3,5,8,13,21… plus a hundred more and asked for the SMALLEST circuit that outputted these numbers, it would not be a circuit of size hundred of bits. The size would be a few bits, and it would be the formula for generating the Fibonacci numbers. Except, instead of doing any thinking to figure this out, you would just use your NP machine to figure it out. And essentially all mathematical theorems would be proved in the same way.
I wasn’t talking about mathematical theorems but about
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.
Pun intended?