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?