Strongly-polynomial time explained

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 integer or rational numbers. It is particularly common in optimization.

Computational models

Two common computational models are the Turing-machine model and the arithmetic model:

• 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

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.

Definition

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. The algorithm runs in strongly polynomial time if:

1. the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
2. the space used by the algorithm is bounded by a polynomial in the size of the input.

Any algorithm with these two properties can be converted to a polynomial time algorithm by replacing the arithmetic operations by suitable algorithms for performing the arithmetic operations on a Turing machine. The second condition is strictly necessary: given the integer

2 ^{n} (which takes up space proportional to n in the Turing machine model), it is possible to compute 2 ^{2 ^{n}} with n multiplications using repeated squaring. However, the space used to represent 2 ^{2 ^{n}} is proportional to 2 ^{n} , and thus exponential rather than polynomial in the space used to represent the input. Hence, it is not possible to carry out this computation in polynomial time on a Turing machine, but it is possible to compute it by polynomially many arithmetic operations.

However, for the first condition, there are algorithms that run in a number of Turing machine steps bounded by a polynomial in the length of binary-encoded input, but do not take a number of arithmetic operations bounded by a polynomial in the number of input numbers. The Euclidean algorithm for computing the greatest common divisor of two integers is one example. Given two integers

a and b , the algorithm performs O( log a + log b) arithmetic operations on numbers with at most O( log a + log b) bits. 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. Its real running time depends on the lengths of a and b in bits and not only on the number of integers in the input.

An algorithm that runs in polynomial time but that is not strongly polynomial is said to run in weakly polynomial time.^[1] 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.

Subtleties

In order to specify the arithmetic model, there are several ways to define the division operation. The outcome of dividing an integer a by another integer b could be one of:

1. The rational number a/b (i.e., not reduced, since reduction cannot be done in strongly-polynomial time).
2. The rational number a/b, except if it is known in advance that a/b is an integer, in which case it is the integer a/b.
3. The rational number a/b, except if a/b is an integer, in which case it is the integer a/b.
4. The integer floor(a/b).

In all versions, strongly-polynomial-time implies polynomial-time in the Turing model.

Notes and References

1. Book: Schrijver, Alexander . Combinatorial Optimization: Polyhedra and Efficiency . Springer . 2003 . 3-540-44389-4 . 1 . Preliminaries on algorithms and Complexity . Alexander Schrijver.