<p>One nice example is the Hamiltonian Path problem is easily solvable in $O(2^n(n+m))$ time (Bellman, 1962) by dynamic programming over vertex subsets. In 2010 <a href="http://epubs.siam.org/doi/10.1137/110839229" rel="nofollow noreferrer">Björklund</a> gave an algorithm running in time $O(1.657^n)$ using determinants and polynomial identity testing in a field of characteristic $2$.</p>

<p>Another example is that of “connectivity problems”, such as Hamiltonian Path, Steiner Tree, or Feedback Vertex Set on graphs of treewidth $k$. The naive dynamic programming algorithms for these problems run in time $2^{O(k \log k)}n^{O(1)}$, and at a glance it really looks like that is what the ``correct’’ running time for these problems should be. However, in a wonderful paper, <a href="https://arxiv.org/abs/1103.0534" rel="nofollow noreferrer">Cygan et al.</a> showed that these problems all allow algorithms with running time $2^{O(k)}n^{O(1)}$, again cleverly using polynomial identity testing in a field of characteristic 2. </p>

CC BY-SA 3.0
2018-02-15T21:32:59.673Z
2018-02-15T21:32:59.673Z
daniello
<p>I am not sure that the below question asked by me several years ago is suitable. </p>

<p><a href="https://mathoverflow.net/questions/153475">https://mathoverflow.net/questions/153475</a></p>

<p>If we use naive dynamic programming, the complexity will be $\Omega(k n^2)$ (I am not sure whether it is $\Theta(k n^2)$ or $\Theta(k n^3)$). Whereas using the fact mentioned in the post (i.e. the linear recurrence relation), we can solve it in $\mathcal{O}(k^2 \log k \log n)$ time since the order of recurrence is $\mathcal{O}(k^2)$ and computing the $n$-th term of a linear recurrence sequence of order $m$ can be achieved in $\mathcal{O}(m \log m \log n)$ time.</p>

CC BY-SA 3.0
2017-09-18T08:07:28.640Z
2017-09-18T08:07:28.640Z
Lwins
<p>The bounded knapsack problem is: you are given n types of items, you have ui items of i-th type, and each item of i-th type weighs wi and costs ci. What is the maximal cost you can get by picking some items weighing at most W in total?</p>

<p>The link provides the solution in O(W*n).</p>

<p><a href="http://petr-mitrichev.blogspot.com/2011/07/integral-bounded-knapsack-problem.html" rel="nofollow noreferrer">http://petr-mitrichev.blogspot.com/2011/07/integral-bounded-knapsack-problem.html</a></p>

CC BY-SA 3.0
2017-09-18T07:56:01.583Z
I would like to think that this answer is not quite suitable for the OP's question.
Lwins
CC BY-SA 3.0
2017-08-19T04:39:37.970Z
2017-08-19T04:39:37.970Z
Prasoon Trivedi
<p>Let $p(n)$ denote the number of <a href="https://en.wikipedia.org/wiki/Partition_(number_theory)#Algorithm" rel="noreferrer">partitions</a> of $n\in\mathbb{N}$ (briefly, number of ways to split a pile of $n$ stones into $\geq1$ unordered nonempty parts). The classical dynamic programming algorithm to find $p(n)$ is to construct a square table $A$ where
$$A_{i,j} = \text{partitions of $i$ where each part is $\leq j$}$$
and recursively fill it using the rules 
$$A_{i,j} = A_{i,j-1} \text{ if }j&gt;i$$
and 
$$A_{i,j} = A_{i,j-1} + A_{i-j,j}\text{ otherwise}$$
with the appropriate conventions for the corner cases. Then $p(n)=A_{n,n}$. This takes $O(n^2)$ operations on integers (let's say we're looking for $p(n)$ modulo some big number, so the size of the numbers is $O(1)$). We can optimize the memory down to $O(n)$ by noticing that we only need the previous column to find the next one.</p>

<p><em>However</em>, the <a href="https://en.wikipedia.org/wiki/Pentagonal_number_theorem" rel="noreferrer">pentagonal number theorem</a> due to Euler says that 
$$p(n) = \sum_{k\in\mathbb{Z}:g_k\leq n}(-1)^{k+1}p(n-g_k)$$
where $g_k = k(3k-1)/2$ are the <strong>pentagonal numbers</strong>. This allows us to recursively build a one-dimensional list of the $p(i)$, using only $O(n\sqrt{n})$ operations, since the above sum contains $O(\sqrt{n})$ terms.</p>

<p><strong>My question:</strong> I was wondering if there are other examples of natural problems for which there is such a surprising speed-up over the standard dynamic programming algorithm, or if this is more of an isolated case complexity-wise.</p>

CC BY-SA 3.0
2016-05-08T22:47:13.137Z
Does the theorem that the numbers in Pascal's triangle (a quadratic-time dynamic program) can instead be computed by a quotient of factorials count as an answer? Or is that too well known to be surprising?
David Eppstein
CC BY-SA 3.0
2016-05-09T06:33:14.957Z
@amakelov I think Hardy–Ramanujan–Rademacher formula gives $O(n^{1/2+\epsilon})$ complexity.
Turbo
CC BY-SA 3.0
2016-05-09T06:50:33.447Z
Isn't this the whole point of P vs NP whether cancellations give exp time advantae for complete problem?
Turbo
CC BY-SA 3.0
2016-05-09T18:20:17.297Z
@DavidEppstein: yes, good point. It does feel less surprising, but in a way that's hard to pin down. I guess the vague motivation behind the entire question was whether we can come up with conditions on problems that capture when we can have such surprising improvements over very simple dynamic programming algorithms. There are some problems, e.g. [all pairs shortest paths](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) where it's open whether such improvements exist.
amakelov
CC BY-SA 3.0
2016-05-09T18:24:49.557Z
@Turbo: for the purposes of this question, I'd be happy to ignore $\textbf{NP}$ and just focus on fine-grained complexity in $\textbf{P}$; I'm interested in questions of the sort, 'why haven't we been able to find an $O(n^{3-\varepsilon})$ algorithm for all pairs shortest paths, while for some other problems there exist surprising ways to improve naive dynamic programming
amakelov
CC BY-SA 3.0
2016-05-09T21:42:25.123Z
I expect that [JeffE](http://cstheory.stackexchange.com/users/111) will have some comments if not an answer on this question. :)
Kaveh
<cc.complexity-theory><ds.algorithms><dynamic-programming>
Beating naive dynamic programming: examples similar to integer partitions?
amakelov
# Beating naive dynamic programming: examples similar to integer partitions?

(Asked by: username_0 on 2016-05-08)

Let $p(n)$ denote the number of [partitions](https://en.wikipedia.org/wiki/Partition_(number_theory)#Algorithm) of $n\in\mathbb{N}$ (briefly, number of ways to split a pile of $n$ stones into $\geq1$ unordered nonempty parts). The classical dynamic programming algorithm to find $p(n)$ is to construct a square table $A$ where
$$A\_{i,j} = \text{partitions of $i$ where each part is $\leq j$}$$
and recursively fill it using the rules
$$A\_{i,j} = A\_{i,j-1} \text{ if }j>i$$
and
$$A\_{i,j} = A\_{i,j-1} + A\_{i-j,j}\text{ otherwise}$$
with the appropriate conventions for the corner cases. Then $p(n)=A\_{n,n}$. This takes $O(n^2)$ operations on integers (let's say we're looking for $p(n)$ modulo some big number, so the size of the numbers is $O(1)$). We can optimize the memory down to $O(n)$ by noticing that we only need the previous column to find the next one.

*However*, the [pentagonal number theorem](https://en.wikipedia.org/wiki/Pentagonal_number_theorem) due to Euler says that
$$p(n) = \sum\_{k\in\mathbb{Z}:g\_k\leq n}(-1)^{k+1}p(n-g\_k)$$
where $g\_k = k(3k-1)/2$ are the **pentagonal numbers**. This allows us to recursively build a one-dimensional list of the $p(i)$, using only $O(n\sqrt{n})$ operations, since the above sum contains $O(\sqrt{n})$ terms.

**My question:** I was wondering if there are other examples of natural problems for which there is such a surprising speed-up over the standard dynamic programming algorithm, or if this is more of an isolated case complexity-wise.

**Tags:** cc.complexity-theory, ds.algorithms, dynamic-programming

> **Comments:**
> **username_1**: Does the theorem that the numbers in Pascal's triangle (a quadratic-time dynamic program) can instead be computed by a quotient of factorials count as an answer? Or is that too well known to be surprising?  
> **username_2**: @username_0 I think Hardy–Ramanujan–Rademacher formula gives $O(n^{1/2+\epsilon})$ complexity.  
> **username_2**: Isn't this the whole point of P vs NP whether cancellations give exp time advantae for complete problem?  
> **username_0**: @DavidEppstein: yes, good point. It does feel less surprising, but in a way that's hard to pin down. I guess the vague motivation behind the entire question was whether we can come up with conditions on problems that capture when we can have such surprising improvements over very simple dynamic programming algorithms. There are some problems, e.g. [all pairs shortest paths](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) where it's open whether such improvements exist.  
> **username_0**: @username_2: for the purposes of this question, I'd be happy to ignore $\textbf{NP}$ and just focus on fine-grained complexity in $\textbf{P}$; I'm interested in questions of the sort, 'why haven't we been able to find an $O(n^{3-\varepsilon})$ algorithm for all pairs shortest paths, while for some other problems there exist surprising ways to improve naive dynamic programming  
> **username_3**: I expect that [JeffE](http://cstheory.stackexchange.com/users/111) will have some comments if not an answer on this question. :)  

---

## 3 answers

### Answer by username_4 on 2018-02-15. Score: 2

One nice example is the Hamiltonian Path problem is easily solvable in $O(2^n(n+m))$ time (Bellman, 1962) by dynamic programming over vertex subsets. In 2010 [Björklund](http://epubs.siam.org/doi/10.1137/110839229) gave an algorithm running in time $O(1.657^n)$ using determinants and polynomial identity testing in a field of characteristic $2$.

Another example is that of “connectivity problems”, such as Hamiltonian Path, Steiner Tree, or Feedback Vertex Set on graphs of treewidth $k$. The naive dynamic programming algorithms for these problems run in time $2^{O(k \log k)}n^{O(1)}$, and at a glance it really looks like that is what the ``correct’’ running time for these problems should be. However, in a wonderful paper, [Cygan et al.](https://arxiv.org/abs/1103.0534) showed that these problems all allow algorithms with running time $2^{O(k)}n^{O(1)}$, again cleverly using polynomial identity testing in a field of characteristic 2.


---

### Answer by username_5 on 2017-09-18. Score: 0

I am not sure that the below question asked by me several years ago is suitable.

<https://mathoverflow.net/questions/153475>

If we use naive dynamic programming, the complexity will be $\Omega(k n^2)$ (I am not sure whether it is $\Theta(k n^2)$ or $\Theta(k n^3)$). Whereas using the fact mentioned in the post (i.e. the linear recurrence relation), we can solve it in $\mathcal{O}(k^2 \log k \log n)$ time since the order of recurrence is $\mathcal{O}(k^2)$ and computing the $n$-th term of a linear recurrence sequence of order $m$ can be achieved in $\mathcal{O}(m \log m \log n)$ time.


---

### Answer by username_6 on 2017-08-19. Score: -1

The bounded knapsack problem is: you are given n types of items, you have ui items of i-th type, and each item of i-th type weighs wi and costs ci. What is the maximal cost you can get by picking some items weighing at most W in total?

The link provides the solution in O(W\*n).

<http://petr-mitrichev.blogspot.com/2011/07/integral-bounded-knapsack-problem.html>

> **Comments:**
> **username_5**: I would like to think that this answer is not quite suitable for the OP's question.  

---

