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.
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 integer or rational numbers.
For example: 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.
Strongly polynomial time is defined in the arithmetic model of computation.
In this model of computation the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform, regardless of the sizes of the operands.
(which takes up space proportional to n in the Turing machine model), it is possible to compute
The Euclidean algorithm for computing the greatest common divisor of two integers is one example.
At the same time, the number of arithmetic operations cannot be bounded by the number of integers in the input (which is constant in this case, there are always only two integers in the input).
Due to the latter observation, the algorithm does not run in strongly polynomial time.
In order to specify the arithmetic model, there are several ways to define the division operation.