algorithm - polinomial - problem np

¿Qué es el tiempo pseudopolinomial? ¿Cómo difiere del tiempo polinomial?

Question

¿Qué es el tiempo pseudopolinomial ? ¿Cómo difiere del tiempo polinomial? Algunos algoritmos que se ejecutan en tiempo pseudopolinomial tienen tiempos de ejecución como O (nW) (para el problema de mochila 0/1 ) u O (√n) (para la división de prueba ); ¿Por qué eso no cuenta como tiempo polinomial?

Answer 1

La complejidad del tiempo pseudopolinomial significa polinomio en el valor / magnitud de la entrada pero exponencial en el tamaño de la entrada.

Por tamaño queremos decir la cantidad de bits necesarios para escribir la entrada.

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

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n) //
Knapsack capacity (W)
for w from 0 to W
do m[0, w] := 0
end for
for i from 1 to n do
for j from 0 to W do
if j >= w[i] then
m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
else
m[i, j] := m[i-1, j]
end if
end for
end for

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

Seamos número de bits necesarios para representar W

i.e. size of input= s =log(W) (log= log base 2)
-> 2^(s)=2^(log(W))
-> 2^(s)=W (because 2^(log(x)) = x)

Ahora, running time of knapsack knapsack = O (nW) = O (n * 2 ^ s) que no es polinomial.

Answer 2

Para comprender la diferencia entre el tiempo polinomial y el tiempo pseudopolinomial, debemos comenzar por formalizar lo que significa "tiempo polinomial".

La intuición común para el tiempo polinomial es "tiempo O (n ^k ) para algunos k". Por ejemplo, la ordenación de selección se ejecuta en el tiempo O (n ² ), que es el tiempo polinomial, mientras que la resolución de fuerza bruta TSP toma tiempo O (n · n!), Que no es tiempo polinomial.

Estos tiempos de ejecución se refieren a alguna variable n que rastrea el tamaño de la entrada. Por ejemplo, en la ordenación por selección, n se refiere a la cantidad de elementos en la matriz, mientras que en TSP n se refiere a la cantidad de nodos en la gráfica. Para estandarizar la definición de lo que "n" significa realmente en este contexto, la definición formal de complejidad temporal define el "tamaño" de un problema de la siguiente manera:

El tamaño de la entrada a un problema es la cantidad de bits necesarios para escribir esa entrada.

Por ejemplo, si la entrada a un algoritmo de clasificación es una matriz de enteros de 32 bits, entonces el tamaño de la entrada sería 32n, donde n es el número de entradas en la matriz. En un gráfico con n nodos y m bordes, la entrada puede especificarse como una lista de todos los nodos, seguida de una lista de todos los bordes, lo que requeriría Ω (n + m) bits.

Dada esta definición, la definición formal de tiempo polinomial es la siguiente:

Un algoritmo se ejecuta en tiempo polinomial si su tiempo de ejecución es O (x ^k ) para alguna constante k, donde x denota el número de bits de entrada dados al algoritmo.

Cuando se trabaja con algoritmos que procesan gráficos, listas, árboles, etc., esta definición está más o menos de acuerdo con la definición convencional. Por ejemplo, supongamos que tiene un algoritmo de clasificación que ordena matrices de enteros de 32 bits. Si utiliza algo así como la ordenación de selección para hacer esto, el tiempo de ejecución, como una función del número de elementos de entrada en la matriz, será O (n ² ). Pero, ¿cómo se corresponde n, la cantidad de elementos en la matriz de entrada, con el número de bits de entrada? Como se mencionó anteriormente, la cantidad de bits de entrada será x = 32n. Por lo tanto, si expresamos el tiempo de ejecución del algoritmo en términos de x en lugar de n, obtenemos que el tiempo de ejecución es O (x ² ), por lo que el algoritmo se ejecuta en tiempo polinomial.

De manera similar, suponga que hace una búsqueda de profundidad en un gráfico, que toma tiempo O (m + n), donde m es el número de aristas en el gráfico y n es el número de nodos. ¿Cómo se relaciona esto con la cantidad de bits de entrada? Bien, si suponemos que la entrada se especifica como una lista de adyacencia (una lista de todos los nodos y bordes), entonces como se mencionó anteriormente, el número de bits de entrada será x = Ω (m + n). Por lo tanto, el tiempo de ejecución será O (x), por lo que el algoritmo se ejecuta en tiempo polinomial.

Las cosas se rompen, sin embargo, cuando comenzamos a hablar de algoritmos que operan en números. Consideremos el problema de probar si un número es primo o no. Dado un número n, puede probar si n es el primero utilizando el siguiente algoritmo:

function isPrime(n):
for i from 2 to n - 1:
if (n mod i) = 0, return false
return true

Entonces, ¿cuál es la complejidad del tiempo de este código? Bueno, ese bucle interno ejecuta O (n) veces y cada vez hace una cantidad de trabajo para calcular n mod i (como un límite superior realmente conservador, esto ciertamente se puede hacer en el tiempo O (n ³ )). Por lo tanto, este algoritmo general se ejecuta en el tiempo O (n ⁴ ) y posiblemente mucho más rápido.

En 2004, tres informáticos publicaron un documento llamado PRIMES en P, que proporciona un algoritmo de tiempo polinomial para comprobar si un número es primo. Fue considerado un resultado histórico. ¿Así que cuál es el problema? ¿No tenemos ya un algoritmo de tiempo polinomial para esto, es decir, el de arriba?

Lamentablemente, no lo hacemos. Recuerde, la definición formal de la complejidad del tiempo se refiere a la complejidad del algoritmo como una función del número de bits de entrada. Nuestro algoritmo se ejecuta en el tiempo O (n ⁴ ), pero ¿qué es eso en función del número de bits de entrada? Bueno, escribir el número n toma O (log n) bits. Por lo tanto, si permitimos que x sea la cantidad de bits necesarios para escribir la entrada n, el tiempo de ejecución de este algoritmo es en realidad O (2 ^4x ), que no es un polinomio en x.

Este es el corazón de la distinción entre el tiempo polinomial y el tiempo pseudopolinomial. Por un lado, nuestro algoritmo es O (n ⁴ ), que se parece a un polinomio, pero por otro lado, bajo la definición formal de tiempo polinomial, no es tiempo polinomial.

Para obtener una intuición de por qué el algoritmo no es un algoritmo de tiempo polinomial, piense en lo siguiente. Supongamos que quiero que el algoritmo tenga que trabajar mucho. Si escribo una entrada como esta:

10001010101011

luego tomará una cantidad de tiempo del peor caso, digamos T , para completar. Si ahora agrego un solo bit al final del número, así:

100010101010111

El tiempo de ejecución ahora (en el peor de los casos) será 2T. ¡Puedo duplicar la cantidad de trabajo que hace el algoritmo simplemente agregando un bit más!

Un algoritmo se ejecuta en tiempo pseudopolinomial si el tiempo de ejecución es un polinomio en el valor numérico de la entrada , en lugar de en el número de bits necesarios para representarlo. Nuestro algoritmo de prueba principal es un algoritmo de tiempo pseudopolinomial, ya que se ejecuta en el tiempo O (n ⁴ ), pero no es un algoritmo de tiempo polinomial porque, en función del número de bits x necesarios para escribir la entrada, el tiempo de ejecución es O (2 ^4x ). La razón por la cual el papel "PRIMES está en P" fue tan significativo fue que su tiempo de ejecución fue (aproximadamente) O (log ¹² n), que en función del número de bits es O (x ¹² ).

Entonces, ¿por qué es importante? Bueno, tenemos muchos algoritmos de tiempo pseudopolinomiales para factorizar enteros. Sin embargo, estos algoritmos son, técnicamente hablando, algoritmos de tiempo exponencial. Esto es muy útil para la criptografía: si desea utilizar el cifrado RSA, debe ser capaz de confiar en que no podemos factorizar fácilmente los números. Al aumentar el número de bits en los números a un valor enorme (digamos, 1024 bits), puede hacer que la cantidad de tiempo que debe tomar el algoritmo de factorización de tiempo pseudopolinómico sea tan grande que sería completamente imposible factorizar el números. Si, por otro lado, podemos encontrar un algoritmo de factorización de tiempo polinomial , este no es necesariamente el caso. Agregar más bits puede hacer que el trabajo crezca mucho, pero el crecimiento será solo de crecimiento polinomial, no de crecimiento exponencial.

Dicho esto, en muchos casos los algoritmos de tiempo pseudopolinomiales están perfectamente bien porque el tamaño de los números no será demasiado grande. Por ejemplo, el recuento de ordenación tiene el tiempo de ejecución O (n + U), donde U es el número más grande en la matriz. Este es el tiempo pseudopolinomial (porque el valor numérico de U requiere bits O (log U) para escribir, por lo que el tiempo de ejecución es exponencial en el tamaño de entrada). Si restringimos artificialmente a U para que U no sea demasiado grande (digamos, si dejamos que U sea 2), entonces el tiempo de ejecución es O (n), que en realidad es un tiempo polinomial. Así es como funciona radix sort : procesando los números de a bit por vez, el tiempo de ejecución de cada ronda es O (n), por lo que el tiempo de ejecución general es O (n log U). Esto en realidad es un tiempo polinomial, porque escribir n números para ordenar usa Ω (n) bits y el valor de log U es directamente proporcional al número de bits necesarios para escribir el valor máximo en la matriz.

¡Espero que esto ayude!