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 una función polinomial del tamaño de la 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 la 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 radica en si las entradas de los algoritmos consisten en números enteros o racionales. Esto es particularmente común en la optimización .

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 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 calcula${\displaystyle 2^{2^{n}}}$mediante repetidas ejecuciones de elevación al cuadrado en tiempo polinomial en el modelo aritmético, pero no en el modelo de Turing. Esto se debe a que el número de bits necesarios para representar el resultado es exponencial con respecto al tamaño de la entrada.

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 con respecto al número de valores de entrada, entonces siempre se ejecutará en tiempo polinomial en el modelo de Turing. Se dice que dicho algoritmo se ejecuta en tiempo fuertemente polinomial .

El tiempo fuertemente polinomial se define en el modelo aritmético de computación . En este modelo, 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 computación está limitado por un polinomio en el número de 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 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${\displaystyle 2^{n}}$(que ocupa un espacio proporcional a n en el modelo de máquina de Turing), es posible calcular${\displaystyle 2^{2^{n}}}$con n multiplicaciones usando elevación al cuadrado repetida . Sin embargo, el espacio utilizado para representar${\displaystyle 2^{2^{n}}}$es proporcional a${\displaystyle 2^{n}}$y, por lo tanto, exponencial en lugar de polinomial en el espacio utilizado para representar la entrada. Por consiguiente, no es posible realizar este cálculo en tiempo polinomial en una máquina de Turing, pero sí es posible calcularlo mediante un número polinomial de operaciones aritméticas.

Sin embargo, para la primera condición, existen 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 requieren 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 enteros es un ejemplo. Dados dos enteros${\displaystyle a}$y${\displaystyle b}$, el algoritmo realiza${\displaystyle O(\log a+\log b)}$operaciones aritméticas con números con como máximo${\displaystyle O(\log a+\log b)}$bits. Al mismo tiempo, el número de operaciones aritméticas no puede estar limitado por el número de enteros en la entrada (que es constante en este caso, siempre hay solo dos enteros en la entrada). Debido a esta última observación, el algoritmo no se ejecuta en tiempo fuertemente polinomial. Su tiempo de ejecución real depende de las longitudes de${\displaystyle a}$y${\displaystyle b}$en bits y no solo en función del número de enteros en la entrada.

Un algoritmo que se ejecuta en tiempo polinomial pero que no es fuertemente polinomial se denomina de 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 un tiempo polinomial.