Strongly-polynomial time

In computer science, a polynomial-time algorithm is – generally speaking – an algorithm whose running time is upper-bounded by some polynomial function of the input size. The definition naturally depends on the computational model, which determines how the running time is measured, and how the input size is measured. Two prominent computational models are the Turing-machine model and the arithmetic model. A strongly-polynomial time algorithm is polynomial in both models, whereas a weakly-polynomial time algorithm is polynomial only in the Turing machine model.

The difference between strongly- and weakly-polynomial time is when the inputs to the algorithms consist of integers or rational numbers. It is particularly common in optimization.

Two common computational models are the Turing-machine model and the arithmetic model:^[1]:32

• In the arithmetic model, every real number requires a single memory cell, whereas in the Turing model the storage size of a real number depends on the number of bits required to represent it.
• In the arithmetic model, every basic arithmetic operation on real numbers (addition, subtraction, multiplication, and division) can be done in a single step, whereas in the Turing model the run-time of each arithmetic operation depends on the length of the operands.

Some algorithms run in polynomial time in one model but not in the other one. For example:

• The Euclidean algorithm runs in polynomial time in the Turing model, but not in the arithmetic model.
• The algorithm that reads n numbers and then computes ${\displaystyle 2^{2^{n}}}$ by repeated squaring runs in polynomial time in the Arithmetic model, but not in the Turing model. This is because the number of bits required to represent the outcome is exponential in the input size.

However, if an algorithm runs in polynomial time in the arithmetic model, and in addition, the binary length of all inputs, outputs, and intermediate values is polynomial in the number of input values, then it is always polynomial-time in the Turing model. Such an algorithm is said to run in strongly polynomial time.

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.

An algorithm that runs in polynomial time but that is not strongly polynomial is said to run in weakly polynomial time.^[2] A well-known example of a problem for which a weakly polynomial-time algorithm is known, but is not known to admit a strongly polynomial-time algorithm, is linear programming. Weakly polynomial time should not be confused with pseudo-polynomial time, which depends on the magnitudes of values in the problem instead of the lengths and is not truly polynomial time.