5
$\begingroup$

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?

$\endgroup$
3
  • $\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, 2013 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, 2013 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, 2013 at 12:48

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2013 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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