Tiempo fuertemente polinomial

En informática , un algoritmo de tiempo polinomial 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 depende naturalmente 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 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 solo en el modelo de máquina de Turing.

La diferencia entre el tiempo fuertemente polinomial y el débilmente polinomial es cuando las entradas de los algoritmos consisten en números enteros o racionales. Es particularmente común en la optimización .

Modelos computacionales

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

En el modelo aritmético, cada número real requiere una sola celda de memoria, mientras que en el modelo de Turing el tamaño de almacenamiento de un número real depende de la cantidad 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 polinómico 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 realiza los cálculos elevando al cuadrado repetidamente se ejecuta en tiempo polinómico 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. $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 polinomial 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 tiempo fuertemente polinomial .

Definición

El tiempo fuertemente polinomial se define en el modelo aritmético de cálculo . 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]

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
El espacio utilizado por el algoritmo está limitado por un polinomio del tamaño de la entrada.

Cualquier algoritmo con estas dos propiedades puede convertirse 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 entero (que ocupa un espacio proporcional a n en el modelo de la máquina de Turing), es posible calcular con n multiplicaciones utilizando cuadrados repetidos . Sin embargo, el espacio utilizado para representar es proporcional a , y por lo tanto exponencial en lugar de polinomial 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 es posible calcularlo mediante un número polinomial de operaciones aritméticas. ${\estilo de visualización 2^{n}}$ $2^{2^{n}}$ $2^{2^{n}}$ ${\estilo de visualización 2^{n}}$

Sin embargo, para la primera condición, hay algoritmos que se ejecutan en un número de pasos de máquina de Turing limitado por un polinomio en la longitud de la entrada codificada en binario, pero no toman un número de operaciones aritméticas limitado por un polinomio en el número de números de entrada. 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 en 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 la última observación, el algoritmo no se ejecuta en tiempo fuertemente polinomial. Su tiempo de ejecución real depende de las longitudes de y en bits y no solo del número de números enteros en la entrada. ${\estilo de visualización a}$ ${\estilo de visualización b}$ $O(\log a+\log b)$ $O(\log a+\log b)$ ${\estilo de visualización a}$ ${\estilo de visualización 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 polinomial no debe confundirse con el tiempo pseudopolinomial , que depende de las magnitudes de los valores en el problema en lugar de las longitudes y no es verdaderamente tiempo polinomial.

Sutilezas

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

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

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

Referencias

^ abc 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, Sr. 1261419
^ Schrijver, Alexander (2003). "Preliminares sobre algoritmos y complejidad". Optimización combinatoria: poliedros y eficiencia . Vol. 1. Springer. ISBN 3-540-44389-4.