This is a difficult question to answer, of course, because you’re asking such a broad question and it’s going to depend on stuff like the actual distribution rather than worst-case, unless you define a class so narrow that each instance offers some gains on every other instance, which is unusual. No-free-lunch, etc. Sometimes there are big savings (this comes up in cryptography where entities like the NSA can attack the world for a lot cheaper than you would think based on the computational cost of individual attacks), but usually there isn’t—AFAIK there is no general way to solve 1 arbitrary 3-SAT problem and get a gain on another. Only if there is some sort of similarity, say, because they are all based on real-world problems (which is much narrower than ‘every logically possible problem’), can you hope to, say, distill the search into a neural net blackbox and amortize gains.
You probably want to look into algorithmic information theory; something like OOPS would be relevant here because it can solve every problem, building on Levin search, and attempts to share or amortize between multiple problems. (This also more closely resembles what you’re really interested in, which is doing this online as you solve problems.)
This is a difficult question to answer, of course, because you’re asking such a broad question and it’s going to depend on stuff like the actual distribution rather than worst-case, unless you define a class so narrow that each instance offers some gains on every other instance, which is unusual. No-free-lunch, etc. Sometimes there are big savings (this comes up in cryptography where entities like the NSA can attack the world for a lot cheaper than you would think based on the computational cost of individual attacks), but usually there isn’t—AFAIK there is no general way to solve 1 arbitrary 3-SAT problem and get a gain on another. Only if there is some sort of similarity, say, because they are all based on real-world problems (which is much narrower than ‘every logically possible problem’), can you hope to, say, distill the search into a neural net blackbox and amortize gains.
You probably want to look into algorithmic information theory; something like OOPS would be relevant here because it can solve every problem, building on Levin search, and attempts to share or amortize between multiple problems. (This also more closely resembles what you’re really interested in, which is doing this online as you solve problems.)