# How do I convert a pseudo-polynomial algorithm to its equivalent exponential form?

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

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

• Psuedo-polynomial algorithms are already exponential in the input length. What do you mean by "explicit"?
– Jake
Jun 15 at 16:25
• @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?
– Frax
Jun 15 at 21:26
• 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. Jun 16 at 18:21
• @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?
– Frax
Jun 16 at 18:51