Complejidad del tiempo del algoritmo Bellman-Held-Karp para TSP, toma 2

Una pregunta reciente discutió el algoritmo de programación dinámica ahora clásico para TSP, debido independientemente a Bellman y Held-Karp . Universalmente se informa que el algoritmo se ejecuta en tiempo $O(2^n n^2)$ . Sin embargo, como señaló recientemente uno de mis alumnos, este tiempo de ejecución puede requerir un modelo de computación irrazonablemente poderoso.

Aquí hay una breve descripción del algoritmo. La entrada consiste en un gráfico dirigido $G=(V,E)$ con $n$ vértices y una función de longitud no negativa $\ell\colon E\to\mathbb{R}^+$ . Para cualquier vértice $s$ y $t$ , y cualquier subconjunto $X$ de vértices que excluya $s$ y $t$ , deje que $L(s,X,t)$ denote la longitud del camino hamiltoniano más corto de $s$ a $t$en el subgrafo inducido $G[X\cup\{s,t\}]$ . El algoritmo de Bellman-Held-Karp se basa en la siguiente recurrencia (o como a los economistas y teóricos del control les gusta llamarlo, "ecuación de Bellman"):

Para cualquier vértice , la duración del recorrido óptimo del vendedor itinerante es L ( s , V ∖ { s } , s ) . Debido a que el primer parámetro s es constante en todas las llamadas recursivas, hay Θ ( 2 n n ) subproblemas diferentes, y cada subproblema depende de, como máximo, n otros. Por lo tanto, el algoritmo de programación dinámica se ejecuta en tiempo O ( 2 n n 2 ) .$s$$L(s,V\setminus\{s\}, s)$$s$$\Theta(2^n n)$$n$$O(2^n n^2)$

¿O sí?

El modelo estándar de RAM entera permite la manipulación en tiempo constante de enteros con bits , pero al menos para operaciones aritméticas y lógicas , los enteros más grandes deben dividirse en fragmentos de tamaño de palabra. (De lo contrario, pueden suceder cosas extrañas ). ¿No es esto también cierto para el acceso a direcciones de memoria más largas? Si un algoritmo usa espacio superpolinomial, ¿es razonable suponer que los accesos a la memoria requieren solo un tiempo constante?$O(\log n)$

Para el algoritmo Bellman-Held-Karp en particular, el algoritmo debe transformar la descripción del subconjunto en la descripción del subconjunto X ∖ { v } , para cada v , a fin de acceder a la tabla de memorización. Si los subconjuntos están representados por enteros, estos enteros requieren n bits y, por lo tanto, no pueden manipularse en tiempo constante; Si no están representados por enteros, su representación no se puede usar directamente como un índice en la tabla de memorización.$X$$X\setminus\{v\}$$v$$n$

Entonces: ¿Cuál es el tiempo de ejecución asintótico real del algoritmo Bellman-Held-Karp?

Esta es una respuesta menos matemática que filosófica, pero prefiero pensar en un modelo RAM que permita la manipulación en tiempo constante de enteros con algún número B de bits que es desconocido pero al menos tan grande como , donde S es la cantidad de espacio que requiere el algoritmo. Porque, si los números enteros no fueran tan grandes, ¿cómo podrías siquiera abordar tu memoria? Para los algoritmos de tiempo y espacio polinómicos es lo mismo que los bits O (log n), pero para los algoritmos de espacio exponencial evita el problema.$\log_2 S$

Por supuesto, si S excede la cantidad de memoria que realmente tiene, su algoritmo no se ejecutará en absoluto. O bien, se ejecutará paginando información dentro y fuera de la memoria y debería usar un modelo de jerarquía de memoria en lugar del modelo de RAM.

Hay una discusión sobre este tema en el reciente libro de Fedor V. Fomin y Dieter Kratsch " Algoritmos exponenciales exactos " donde especifican el tiempo de ejecución en el modelo de RAM de costo unitario y el modelo de RAM de costo logarítmico ( - la distancia máxima entre las ciudades y f ( n ) = O ∗ ( g ( n ) ) si f ( n ) = O ( g ( n ) p o l y ( n ) ) ):$W$$f(n)=\mathcal{O}^{\ast}(g(n))$$f(n)=\mathcal{O}(g(n)poly(n))$

y 2 n logW n O ( 1 ) (nota, 2 n logW n O ( 1 ) ∉ O ∗ ( 2 n )), respectivamente.$\mathcal{O}^{\ast}(2^n)$$2^n\log Wn^{\mathcal{O}(1)}$$2^n\log Wn^{\mathcal{O}(1)}\notin\mathcal{O}^{\ast}(2^n)$