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?

  • $\begingroup$ 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. $\endgroup$ – Vor Oct 4 '13 at 10:14
  • $\begingroup$ @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. $\endgroup$ – josejuan Oct 4 '13 at 10:45
  • $\begingroup$ 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. $\endgroup$ – Vor Oct 4 '13 at 12:48

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.

| cite | improve this answer | |
  • $\begingroup$ 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! :) $\endgroup$ – josejuan Oct 4 '13 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.