One $O(n^k)$ algorithm requiring only one $O(2^n)$ computation (for all n instances) is P or NP Let $a$ one decision problem and $A$ one algorithm solving it in $O(n^k)$.

But, to construct $A_n$ we need to compute certain thing (strategy path, magic numbers, ...), we can compute that using certain general algorithm $R$ in $O(2^n)$.

Obiously, $A$ is polynomial (then, all $A_n$ are in P) and $R$ is exponential.

We can not solve big instances because $R$ is not practical.

But, in practice, we will can solve big instances after a big effort computing $A_n = R(n)$.

My question is twofold:


How are such problems considered in theory?
Have they been studied explicitly? Is there a particular case? some literature to read?
How are such problems solved in practice?
Have they been studied in general? Is there is a particular case? some literature to read?
If the "thing" is polynomial-size, then it's in P/poly, a class that has been studied intensively, although this is a very interesting subclass of it which I don't believe been studied. If you have an algorithm that falls into this subclass, I believe theoretical computer scientists might be interested in it.

If the "thing" can be exponential size, then the "thing" could just be a table of all the answers for the instances of size $n$, so all algorithms in EXPTIME would fall into this class. And in fact, this class would be equal to EXPTIME, since the algorithm R followed by A is in EXPTIME.