Time complexity of Bellman-Held-Karp algorithm for TSP, take 2

Question

A recent question discussed the now-classical dynamic programming algorithm for TSP, due independently to Bellman and Held-Karp. The algorithm is universally reported to run in $O(2^n n^2)$ time. However, as one of my students recently pointed out, this running time may require an unreasonably powerful model of computation.

Here is a brief description of the algorithm. The input consists of a directed graph $G=(V,E)$ with $n$ vertices and a non-negative length function $\ell\colon E\to\mathbb{R}^+$. For any vertices $s$ and $t$, and any subset $X$ of vertices that excludes $s$ and $t$, let $L(s,X,t)$ denote the length of the shortest Hamiltonian path from $s$ to $t$ in the induced subgraph $G[X\cup\{s,t\}]$. The Bellman-Held-Karp algorithm is based on the following recurrence (or as economists and control theorists like to call it, “Bellman's equation”):

$$ L(s,X,t) = \begin{cases} \ell(s,t) & \text{if $X = \varnothing_{\strut} $} \\ \min_{v\in X}~ \big(L(s, X\setminus\lbrace v\rbrace, v) + \ell(v,t)\big) & \text{otherwise} \end{cases} $$

For any vertex $s$, the length of the optimal traveling salesman tour is $L(s,V\setminus\{s\}, s)$. Because the first parameter $s$ is constant in all recursive calls, there are $\Theta(2^n n)$ different subproblems, and each subproblem depends on at most $n$ others. Thus, the dynamic programming algorithm runs in $O(2^n n^2)$ time.

Or does it?!

The standard integer RAM model allows constant-time manipulation of integers with $O(\log n)$ bits, but at least for arithmetic and logical operations, larger integers must be broken into word-sized chunks. (Otherwise, strange things can happen.) Is this not also true of access to longer memory addresses? If an algorithm uses superpolynomial space, is it reasonable to assume that memory accesses require only constant time?

For the Bellman-Held-Karp algorithm in particular, the algorithm must transform the description of the subset $X$ into the description of the subset $X\setminus\{v\}$, for each $v$, in order to access the memoization table. If the subsets are represented by integers, these integers require $n$ bits and therefore cannot be manipulated in constant time; if they are not represented by integers, their representation cannot be used directly as an index into the memoization table.

So: What is the actual asymptotic running time of the Bellman-Held-Karp algorithm?

Answer 1

This is less of a mathematical answer than a philosophical one, but I prefer to think of a RAM model that allows constant-time manipulation of integers with some number B of bits that is unknown but at least as large as $\log_2 S$, where S is the amount of space that the algorithm requires. Because, if the integers weren't that big, how could you even address your memory? For polynomial time and space algorithms it's the same as O(log n) bits, but for exponential space algorithms it avoids the problem.

Of course, if S exceeds the amount of memory you actually have, your algorithm won't run at all. Or, it will run by paging information into and out of memory and you should be using a memory hierarchy model instead of the RAM model.

Answer 2

There is a discussion of this issue in the recent book by Fedor V. Fomin and Dieter Kratsch "Exact Exponential Algorithms" where they specify the running time in the unit-cost RAM model and the log-cost RAM model ($W$ - the maximum distance between the cities and $f(n)=\mathcal{O}^{\ast}(g(n))$ if $f(n)=\mathcal{O}(g(n)poly(n))$):

$\mathcal{O}^{\ast}(2^n)$ and $2^n\log Wn^{\mathcal{O}(1)}$ (note, $2^n\log Wn^{\mathcal{O}(1)}\notin\mathcal{O}^{\ast}(2^n)$ ), respectively.