¿Qué es el tiempo pseudopolinomial? ¿En qué se diferencia del tiempo polinomial?

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

Para entender la diferencia entre el tiempo polinomial y el tiempo pseudopolinomial, debemos comenzar formalizando lo que significa "tiempo polinomial".

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

Todos estos tiempos de ejecución se refieren a alguna variable n que rastrea el tamaño de la entrada. Por ejemplo, en el ordenamiento por selección, n se refiere al número de elementos en la matriz, mientras que en TSP n se refiere al número de nodos en el gráfico. Para estandarizar la definición de lo que realmente significa "n" 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 el número 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 podría 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 más o menos concuerda con la definición convencional. Por ejemplo, suponga que tiene un algoritmo de ordenación que ordena matrices de enteros de 32 bits. Si usa algo como el ordenamiento por selección para hacer esto, el tiempo de ejecución, en función del número de elementos de entrada en la matriz, será O (n ² ). Pero, ¿cómo corresponde n, el número de elementos en la matriz de entrada, al número de bits de entrada? Como se mencionó anteriormente, el número 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 realiza una búsqueda en profundidad en un gráfico, lo que lleva 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 el número de bits de entrada dados? Bueno, si asumimos 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.

Sin embargo, las cosas se rompen cuando empezamos a hablar de algoritmos que operan con 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 primo 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 temporal de este código? Bueno, ese ciclo interno se ejecuta O (n) veces y cada vez hace algo de trabajo para calcular n mod i (como 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 científicos informáticos publicaron un artículo llamado PRIMES is in P dando un algoritmo de tiempo polinomial para probar si un número es primo. Se consideró 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?

Desafortunadamente, no lo hacemos. Recuerde, la definición formal de complejidad del tiempo habla de la complejidad del algoritmo en 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 requiere O (log n) bits. Por lo tanto, si dejamos que x sea el número 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 tiempo polinomial y tiempo pseudopolinomial. Por un lado, nuestro algoritmo es O (n ⁴ ), que parece un polinomio, pero por otro lado, bajo la definición formal de tiempo polinomial, no es tiempo polinomial.

Para tener una idea 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, en el peor de los casos, tardará, por ejemplo T, en completarse. 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 algún 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 ^{x 4} ). La razón por la que el artículo "PRIMES is in P" era tan significativo era que su tiempo de ejecución era (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 poder confiar en que no podemos factorizar números fácilmente. Al aumentar la cantidad 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 pseudopolinomial sea tan grande que sería completa y absolutamente inviable 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 solo será un crecimiento polinomial, no un crecimiento exponencial.

Dicho esto, en muchos casos, los algoritmos de tiempo pseudopolinomial están perfectamente bien porque el tamaño de los números no será demasiado grande. Por ejemplo, la ordenación por recuento tiene tiempo de ejecución O (n + U), donde U es el número más grande de la matriz. Este es un tiempo pseudopolinomial (porque el valor numérico de U requiere O (log U) bits para escribir, por lo que el tiempo de ejecución es exponencial en el tamaño de entrada). Si restringimos artificialmente 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 tiempo polinomial. Así es como funciona la ordenación por radix : al procesar los números un bit a la 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 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!

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 nos referimos al número de bits necesarios para escribir la entrada.

A partir del pseudocó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í, sin embargo, W no es polinomio en la longitud de la entrada, que es lo que lo hace pseudopolinomial.

Sea s el 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= O (nW) = O (n * 2 ^ s) que no es polinomio.