Creo que la respuesta principal La respuesta de Victor Costan a ¿Es el algoritmo Bellman-Ford pseudo polinomial? pierde la distinción real, que es el tamaño de entrada . La respuesta principal es correcta, pero no por las mejores razones.
En el problema 0-1 Mochila, el tamaño de entrada de la capacidad [matemática] B [/ matemática] de la instancia de mochila es [matemática] O (\ log_2 {B}) [/ matemática]. Esto se debe a que la capacidad es un número entero que es independiente de los elementos y sus valores, pero es parte de la entrada. El algoritmo de programación dinámica tiene tiempo de ejecución [math] O (Bn). [/ Math] Este algoritmo tiene tiempo de ejecución pseudo-polinomial porque con respecto al tamaño de entrada, [math] B [/ math] es exponencial.
Ahora, vamos al algoritmo de Bellman y Ford. Deje [math] w [/ math] ser el peso de los bordes. El tamaño de entrada del problema de ruta más corta es en realidad [matemática] O (| V | + | E | + \ sum_ {e \ in E} {\ log {w (e)}}) [/ matemática] bajo una codificación razonable . Por lo general, el tamaño de entrada de un gráfico es el número de vértices y / o el número de bordes (si está ponderado, incluya los pesos de los bordes).
- ¿Qué pasaría si alguien prueba P = NP o P! = NP?
- ¿Cuál es la función concatenada en Excel y cuál es su opuesto?
- ¿Cómo se usan las matemáticas en informática?
- Soy un estudiante de estadística que se especializa en informática. ¿Qué recursos en Python necesito para llevar a cabo pruebas de hipótesis, inferencia estadística y gráficos?
- Como estudiante, ¿es inteligente crear mis propias bibliotecas de programación matemática?
- Creo que olvidó que los vértices tienen etiquetas, lo que requiere almacenar números [matemáticos] | V | [/ matemáticos] para las etiquetas (cada uno de un número constante de bits).
- Podemos indicar lo que tengo porque puedes codificar cada borde como dos vértices, cada uno con una etiqueta de número constante de bits.
- Cada vértice será una etiqueta con un número constante de bits.
- Suponiendo que cada peso también tenga un número constante de bits, podemos descartar el último término, pero a veces es valioso mantenerlo allí en caso de que estemos interesados en la distinción entre polinomio fuerte y polinomio débil.
Ahora, mire el tiempo de ejecución del algoritmo, es [math] \ Theta (| V || E |) [/ math]. Esto está lejos de ser pseudo-polinomial, ya que con respecto al tamaño de entrada es definitivamente polinomial. De hecho, el tiempo de ejecución del algoritmo de Bellman y Ford es fuertemente polinomial.
