I have a pseudo-polynomial algorithm that solves a decision problem $D$.
How do I convert it in its "explicit" exponential form?
4
-
$\begingroup$ Psuedo-polynomial algorithms are already exponential in the input length. What do you mean by "explicit"? $\endgroup$– JakeJun 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$– FraxJun 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$– Chandra ChekuriJun 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$– FraxJun 16 at 18:51
Add a comment
|