Si [math] \ Pi [/ math] es un problema y [math] I [/ math] es una instancia del problema, entonces un algoritmo polinómico que resuelve [math] \ Pi [/ math] opera en el polinomio de tiempo en el Representación binaria de [matemáticas] I [/ matemáticas].
Por ejemplo, supongamos que deseo determinar si un número dado [math] n [/ math] exhibe cierta propiedad. Un algoritmo polinómico que resuelva el problema se ejecutará en [matemática] O (m ^ k) [/ matemática] durante algún tiempo [matemática] k [/ matemática], donde [matemática] m [/ matemática] es la longitud de la representación binaria de la entrada [math] n [/ math] (en este caso [math] m = \ lfloor \ log_2 n \ rfloor + 1 [/ math]).
Un algoritmo pseudopolinomial que resuelve un problema [matemática] \ Pi [/ matemática] opera en el tiempo polinomial en la representación unaria (valor numérico) de la entrada [matemática] I [/ matemática]. En nuestro ejemplo anterior, un algoritmo de tiempo pseudo-polinomial tendrá tiempo de ejecución [math] O (n ^ k) [/ math], ya que [math] n [/ math] es la longitud de la representación unaria de [math] n [/ math] ([math] \ underbrace {111 … 1} _ \ textrm {n} [/ math]).
- Cómo crear un cuestionario de matemáticas en Python
- Cómo usar el lenguaje C para escribir un programa para hacer una matriz de multiplicación que permita 1, 2, 3, 4, 5, 6 o 7 hilos que corren paralelos
- ¿Cuánto conocimiento de matemáticas se requiere para ser un programador?
- ¿Cómo puedo calcular los fallos de página a partir de la cadena de referencia y los marcos disponibles?
- ¿Por qué la programación de Erlang aún no ha penetrado en el plan de estudios de ciencias de la computación como cabría esperar?
Ahora que entendemos las definiciones, la pregunta es ¿por qué nos interesan los algoritmos que se ejecutan en el polinomio en el tiempo en el valor numérico de la entrada ? ¡Nuestras computadoras representan datos en binario!
Bueno, resulta que los algoritmos de tiempo pseudo-polinomiales son muy útiles en la construcción de un PTAS (esquema de aproximación de tiempo polinomial) para ciertos problemas ([matemáticos] NP [/ matemáticos] completos). ¿Porqué es eso?
1. El valor numérico de la entrada crece linealmente con el valor de entrada, lo que significa que nuestra métrica para el tamaño ya crece bastante rápido, por lo que los algoritmos de pasos adicionales que pueden necesitar para producir una solución no “agregan mucho” al aumento ya rápido de la métrica Por lo tanto, es más fácil encontrar algoritmos que operen en tiempo pseudo-polinomial.
2. Una vez que encontremos algoritmos de tiempo pseudo-polinomiales, podemos usarlos para resolver eficientemente problemas donde la representación unaria está garantizada por un polinomio en la representación binaria. (Por ejemplo, considere el problema de la mochila, pero con la restricción de que el beneficio asociado con cada elemento está limitado por un polinomio en el número total de elementos disponibles. Podemos usar un algoritmo de tiempo pseudo-polinomial para resolver este problema de manera eficiente).
3. En los casos en que no exista un límite polinómico en el valor (como con problemas generales de [math] NP [/ math]) podemos traducir una instancia de un problema [math] I [/ math] en un nuevo instancia [matemática] I ‘[/ matemática] que está limitada de la manera deseada, sufriendo un error modesto y controlado en el proceso (ya que estamos ignorando algunos bits menos significativos de la entrada para comprimirla). ¡Esto significa que podemos aproximar, con un parámetro de error controlado, soluciones a problemas que de otro modo todavía tenemos que resolver de manera eficiente!
Así es exactamente cómo, por ejemplo, encontramos algoritmos que encuentran soluciones al problema de la Mochila que se acercan arbitrariamente a las soluciones óptimas, es decir, [math] (1- \ epsilon) OPT [/ math], donde los algoritmos operan en tiempo polinomial tanto en el tamaño de la entrada como en [math] 1 / \ epsilon [/ math]. ¡Hurra!
