Beating naive dynamic programming: examples similar to integer partitions?

Let $p(n)$ denote the number of partitions 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 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.

• 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 May 8 '16 at 22:47
• @amakelov I think Hardy–Ramanujan–Rademacher formula gives $O(n^{1/2+\epsilon})$ complexity. – T.... May 9 '16 at 6:33
• Isn't this the whole point of P vs NP whether cancellations give exp time advantae for complete problem? – T.... May 9 '16 at 6:50
• @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 where it's open whether such improvements exist. – amakelov May 9 '16 at 18:20
• @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 May 9 '16 at 18:24

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 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. 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.

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.

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

• I would like to think that this answer is not quite suitable for the OP's question. – Lwins Sep 18 '17 at 7:56