¿Cuál es el significado de la complejidad del tiempo pseudo polinomial? Vi que Knapsack se ejecuta en tiempo pseudo polinomial. Leí sobre esto aquí: tiempo pseudo-polinomial pero no puedo seguirlo. Quiero comprender el concepto de tiempo de ejecución pseudo polinomial y cómo se ejecuta la mochila en tiempo de pseudo polinomio.

La complejidad temporal pseudo-polinomial significa polinomio en el valor / magnitud de la entrada pero exponencial en el tamaño de la entrada.

Por tamaño nos referimos al número de bits requeridos para escribir la entrada.

Del pseudocódigo de la mochila, podemos encontrar que la complejidad del tiempo es O (nW).

  // Entrada:
 // Valores (almacenados en la matriz v) 
 // Pesos (almacenados en la matriz w)
 // Número de elementos distintos (n) //
 Capacidad de mochila (W) 
 para w de 0 a W 
     do m [0, w]: = 0 
 fin para  
 para i de 1 a n do  
         para j de 0 a W do
                si j> = w [i] entonces 
                       m [i, j]: = max (m [i-1, j], m [i-1, jw [i]] + v [i]) 
               más 
                       m [i, j]: = m [i-1, j]
               terminara si
        fin para 
 fin para

Aquí, W no es polinomial en la longitud de la entrada, que es lo que lo hace pseudo- polinomial.

cantidad de bits necesarios para representar W = log (W)
es decir, tamaño de entrada = s (let) = log (W) (log = log base 2)
-> 2 ^ (s) = 2 ^ (log (W))
-> 2 ^ (s) = W (porque 2 ^ (log (x)) = x)

ahora, tiempo de ejecución de mochila = O (nW)
= O (n * 2 ^ s)
que no es polinomio

La mejor explicación que tengo hasta ahora:
¿Qué es el tiempo pseudopolinomial? ¿Cómo difiere del tiempo polinomial?

En lenguaje sencillo:
Un algoritmo es pseudo-polinomial si el algoritmo es polinomial en términos de tamaño de entrada, es decir, n (n números en la matriz) pero es pseudo-polinomial o crece exponencialmente en términos de longitud de entrada, es decir, no. de bits necesarios para almacenar cada elemento en la matriz.
El siguiente video puede ayudarlo con una explicación simple n definición:

Creo que deberías referir esto …
¿Por qué el problema de la mochila es pseudo-polinomial? Incluso si obtuvo la respuesta más votada, obtendrá por qué se llama pseudo-polinomial a tiempo.

Puede verificar Solución – FaaS y complejidad pseudo-polinomial

tiempo de ejecución de la mochila = O (nW)
= O (n * 2 ^ s)
que no es polinomio parece una buena respuesta