5
$\begingroup$

Are there dynamic programming examples that run in exponential time? Every example that I've seen so far constructs the top half of a matrix in a bottom-up fashion ($n^2$) from the base case and evaluates $n$ expressions to optimize each entry.

$\endgroup$
  • $\begingroup$ Just to clarify: are you asking for a particular instance of a particular problem for which a particular implementation of dynamic programming must take exponential time? $\endgroup$ – András Salamon Feb 28 '14 at 10:45
5
$\begingroup$

A well-known example is the Held-Karp dynamic programming approach to solving the traveling salesman problem (TSP), running in $O(n^22^n)$ time and $O(n2^n)$ space. For more, see these notes.

$\endgroup$
4
$\begingroup$

A good example is the dynamic programming algorithm for (integer) SUBSET-SUM, which works in time $O(nT)$, where $n$ is the number of elements and $T$ is the target. The target could be exponential in its length, so in general this runs in exponential time.

$\endgroup$
2
$\begingroup$

Examples can be created artificially. Take any problem for which polynomial running time is not known and apply Dynamic Programming on it. For example, you can take the problem of finding largest independent set in a graph. You can apply DP on it saying a vertex $v_0$ can be in the set or not. This gives two cases. Since this problem is not known to be solvable in polynomial time, you cannot reduce exponential number of calls in DP to polynomial number.

$\endgroup$

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.