Tiempo fuertemente polinomial

En informática , un algoritmo de tiempo polinómico es, en términos generales, un algoritmo cuyo tiempo de ejecución está limitado superiormente por alguna función polinómica del tamaño de entrada. La definición, naturalmente, depende del modelo computacional, que determina cómo se mide el tiempo de ejecución y cómo se mide el tamaño de entrada . Dos modelos computacionales destacados son el modelo de la máquina de Turing y el modelo aritmético . Un algoritmo de tiempo fuertemente polinomial es polinomial en ambos modelos, mientras que un algoritmo de tiempo débilmente polinomial es polinomial sólo en el modelo de máquina de Turing.

La diferencia entre tiempo polinomial fuerte y débil es cuando las entradas a los algoritmos consisten en números enteros o racionales. Es particularmente común en optimización .

Modelos computacionales

Dos modelos computacionales comunes son el modelo de la máquina de Turing y el modelo aritmético : ^{[1] : 32}

• En el modelo aritmético, cada número real requiere una única celda de memoria, mientras que en el modelo de Turing el tamaño de almacenamiento de un número real depende del número de bits necesarios para representarlo.
• En el modelo aritmético, cada operación aritmética básica con números reales (suma, resta, multiplicación y división) se puede realizar en un solo paso, mientras que en el modelo de Turing el tiempo de ejecución de cada operación aritmética depende de la longitud de los operandos.

Algunos algoritmos se ejecutan en tiempo polinomial en un modelo pero no en el otro. Por ejemplo:

• El algoritmo euclidiano se ejecuta en tiempo polinomial en el modelo de Turing, pero no en el modelo aritmético.
• El algoritmo que lee n números y luego los calcula elevando al cuadrado repetidamente se ejecuta en tiempo polinomial en el modelo aritmético, pero no en el modelo de Turing. Esto se debe a que la cantidad de bits necesarios para representar el resultado es exponencial en el tamaño de entrada. ${\displaystyle 2^{2^{n}}}$

Sin embargo, si un algoritmo se ejecuta en tiempo polinomial en el modelo aritmético y, además, la longitud binaria de todas las entradas, salidas y valores intermedios es polinómica en el número de valores de entrada, entonces siempre es tiempo polinomial en el modelo de Turing. . Se dice que un algoritmo de este tipo se ejecuta en un tiempo fuertemente polinomial .

Definición

El tiempo fuertemente polinómico se define en el modelo de cálculo aritmético . En este modelo de cálculo, las operaciones aritméticas básicas (suma, resta, multiplicación, división y comparación) requieren un paso de tiempo unitario para realizarse, independientemente del tamaño de los operandos. El algoritmo se ejecuta en tiempo fuertemente polinomial si: ^[1]

1. el número de operaciones en el modelo aritmético de cálculo está limitado por un polinomio en el número de números enteros en la instancia de entrada; y
2. el espacio utilizado por el algoritmo está limitado por un polinomio en el tamaño de la entrada.

Cualquier algoritmo con estas dos propiedades se puede convertir en un algoritmo de tiempo polinomial reemplazando las operaciones aritméticas por algoritmos adecuados para realizar las operaciones aritméticas en una máquina de Turing . La segunda condición es estrictamente necesaria: dado el número entero (que ocupa un espacio proporcional a n en el modelo de la máquina de Turing), es posible calcular con n multiplicaciones usando elevaciones repetidas al cuadrado . Sin embargo, el espacio utilizado para representar es proporcional a y, por tanto, exponencial en lugar de polinomio en el espacio utilizado para representar la entrada. Por lo tanto, no es posible realizar este cálculo en tiempo polinomial en una máquina de Turing, pero sí es posible calcularlo mediante muchas operaciones aritméticas polinomiales. ${\displaystyle 2^{n}}$ ${\displaystyle 2^{2^{n}}}$ ${\displaystyle 2^{2^{n}}}$ ${\displaystyle 2^{n}}$

Sin embargo, para la primera condición, existen algoritmos que se ejecutan en una cantidad de pasos de la máquina de Turing acotados por un polinomio en la longitud de la entrada codificada en binario, pero no toman una cantidad de operaciones aritméticas acotadas por un polinomio en la cantidad de entradas. números. El algoritmo euclidiano para calcular el máximo común divisor de dos números enteros es un ejemplo. Dados dos números enteros y , el algoritmo realiza operaciones aritméticas con números con como máximo bits. Al mismo tiempo, el número de operaciones aritméticas no puede estar limitado por el número de números enteros en la entrada (que es constante en este caso, siempre hay solo dos números enteros en la entrada). Debido a esta última observación, el algoritmo no se ejecuta en un tiempo fuertemente polinomial. Su tiempo de ejecución real depende de las longitudes y en bits y no sólo del número de números enteros en la entrada. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle O(\log a+\log b)}$ ${\displaystyle O(\log a+\log b)}$ ${\displaystyle a}$ ${\displaystyle b}$

Un algoritmo que se ejecuta en tiempo polinomial pero que no es fuertemente polinomial se dice que se ejecuta en tiempo débilmente polinomial . ^[2] Un ejemplo bien conocido de un problema para el cual se conoce un algoritmo de tiempo débilmente polinomial, pero no se sabe que admita un algoritmo de tiempo fuertemente polinomial, es la programación lineal . El tiempo débilmente polinómico no debe confundirse con el tiempo pseudopolinomial , que depende de las magnitudes de los valores del problema en lugar de las longitudes y no es un tiempo verdaderamente polinomial.

Sutilezas

Para especificar el modelo aritmético, existen varias formas de definir la operación de división. El resultado de dividir un número entero a por otro número entero b podría ser uno de: ^{[1] : 33}

1. El número racional a/b (es decir, no reducido, ya que la reducción no se puede realizar en un tiempo fuertemente polinomial).
2. El número racional a/b, excepto si se sabe de antemano que a/b es un número entero, en cuyo caso es el número entero a/b.
3. El número racional a/b, excepto si a/b es un número entero, en cuyo caso es el número entero a/b.
4. El piso entero (a/b).

En todas las versiones, el tiempo fuertemente polinomial implica tiempo polinomial en el modelo de Turing.

Referencias

1. Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria, Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi :10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, señor  1261419
2. Schrijver, Alejandro (2003). "Preliminares sobre algoritmos y Complejidad". Optimización combinatoria: poliedros y eficiencia . vol. 1. Saltador. ISBN 3-540-44389-4.