# 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 there is a single input $x$ (or even a finite number of inputs) for which we must run $R(x)$ to calculate $A(x)$, then the algorithm $A$ will require $\leq q \, |x'|^k$ steps for all $|x'|>|x|$, so its complexity is $O(|x'|^k)$ i.e. it is polynomial. – Vor Oct 4 '13 at 10:14
• @Vor even for only one input x, at first time, you need compute An=R(n) and it has exponential complexity (that computation is not polynomial). Thanks anyway. – josejuan Oct 4 '13 at 10:45
• sorry, perhaps I didn't understand the question well but if there are only finitely many inputs for which A requires exponential time and on the other inputs $x$ it requires $O(n^k)$ (where $|x|=n$) then the algorithm is polynomial. Perhaps you should clarify exactly what is $n$ (is it the length of the input $x$ of A?). And in this case you should also clarify what is the input of $R$, if it is $n$ then the length of its input is $\log n$, and what is the length of the output. – Vor Oct 4 '13 at 12:48

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.
• Yes! I was looking for P/poly algorithms (and yes, I'm thinking in a polynomial "thing"). Even so, I'm interested when $R(n)$ is in EXP. But is a good starting point. Thank you! :) – josejuan Oct 4 '13 at 14:08