Tiempo pseudopolinomial

Consideremos la solución del problema de comprobar si un número n es primo verificando ingenuamente si un número en${\displaystyle \{2,3,\dots ,{\sqrt {n}}\}}$divide${\displaystyle n}$de manera uniforme. Este enfoque puede tardar hasta${\displaystyle {\sqrt {n}}-1}$divisiones, que es sublineal en el valor de n pero exponencial en la longitud de n (que es aproximadamente${\displaystyle \log(n)}$Por ejemplo, un número n ligeramente inferior a 10 000 000 000 requeriría hasta aproximadamente 100 000 divisiones, aunque la longitud de n sea de tan solo 11 dígitos. Además, es fácil escribir una entrada (por ejemplo, un número de 300 dígitos) para la cual este algoritmo resulta impracticable. Dado que la complejidad computacional mide la dificultad con respecto a la longitud de la entrada (codificada), este algoritmo ingenuo es en realidad exponencial. Sin embargo, su tiempo es pseudopolinomial.

Compare este algoritmo con un verdadero algoritmo numérico polinomial, por ejemplo, el algoritmo sencillo para la suma: Sumar dos números de 9 dígitos requiere alrededor de 9 pasos simples, y en general el algoritmo es verdaderamente lineal en la longitud de la entrada. Comparado con los números reales que se suman (en miles de millones), el algoritmo podría llamarse "tiempo pseudologarítmico", aunque tal término no es estándar. Por lo tanto, sumar números de 300 dígitos no es impráctico. De manera similar, la división larga es cuadrática: un número de m dígitos se puede dividir entre un número de n dígitos en${\displaystyle O(mn)}$pasos (véase la notación Big O ).

En el caso de la primalidad, resulta que existe un algoritmo diferente para comprobar si n es primo (descubierto en 2002) que se ejecuta en tiempo${\displaystyle O((\log {n})^{6})}$.

En el problema de la mochila , se nos da${\displaystyle n}$artículos con peso${\displaystyle w_{i}}$y valor${\displaystyle v_{i}}$junto con una capacidad de peso máxima de una mochila${\displaystyle W}$El objetivo es resolver el siguiente problema de optimización; informalmente, ¿cuál es la mejor manera de colocar los artículos en la mochila para maximizar su valor?

maximizar${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

sujeto a${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$y${\displaystyle x_{i}\in \{0,1\}}$.

Resolver este problema es NP-difícil , por lo que un algoritmo de tiempo polinomial es imposible a menos que P = NP . Sin embargo, un${\displaystyle O(nW)}$El algoritmo de tiempo es posible utilizando programación dinámica ; dado que el número${\displaystyle W}$solo necesita${\displaystyle \log W}$En resumen, este algoritmo se ejecuta en tiempo pseudopolinomial.