I have a pseudo-polynomial algorithm that solves a decision problem $D$.

How do I convert it in its "explicit" exponential form?

  • $\begingroup$ Psuedo-polynomial algorithms are already exponential in the input length. What do you mean by "explicit"? $\endgroup$
    – Jake
    Jun 15 at 16:25
  • $\begingroup$ @Jake I know that, maybe I phrased it wrong. Take for example the Subset sum Problem, it can be solved by a pseudo-polynomial algorithm by dynamic programming, but I can also convert the algorithm to simply creating all subsets of the inputs and checking each one in $O(2^{n}n)$. What's a good approach to do this with a generic pseudo-polynomial algorithm? $\endgroup$
    – Frax
    Jun 15 at 21:26
  • $\begingroup$ If the problem is in NP then you always have an exponential-time algorithm so you can use that algorithm or the pseudo-polytime algorithm depending on the number size. $\endgroup$ Jun 16 at 18:21
  • $\begingroup$ @ChandraChekuri Right, but in my case I have a decision problem for which I only know the pseudo-polynomial algorithm, but I don't know the explicit exponential one. How can I obtain it from the pseudo one? $\endgroup$
    – Frax
    Jun 16 at 18:51


Your Answer

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

Browse other questions tagged or ask your own question.