Specifically, let's say you are handed a Boolean 3-sat problem, and you finally managed to finish solving the 3-SAT instance you are given by a superpolynomially large algorithm.
Now, you are given another Boolean 3-SAT problem. Can you amortize the complexity costs of 3-SAT problems, or does each 3-SAT problem instance require you to pay the full complexity cost of the algorithm you run?
To give an analogy for the question I'm asking, I'm trying to determine whether computationally hard problems are more CapEx dominated, and the OpEx of running each particular instance of 3-sat is low, making it more like an investment, or perhaps buying things, or is it more like a high OpEx, where each instance of a 3-SAT problem remains just as expensive and can't be amortized, much like renting something.
Equivalently, the question is how much you are able to amortize the costs of solving similar problems, like 3-SAT for NP-complete problems or True Quantified Boolean Formulas for PSPACE-complete problems.
Challenge: If you are able to show that you can reduce computational complexity costs via amortizing the instances of a problem, how far up the complexity hierarchy does this go? How complex does a problem need to be before you can't amortize the costs of a computationally complex problem anymore?
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.)