6
$\begingroup$

In [1] strongly-polynomial is defined as either:

  • The algorithm runs in strongly polynomial time if the algorithm is a polynmomial space algorithm and performs a number of elementary arithmetic operations which is bounded by a polynomial in the number of input numbers.
  • A polynomial algorithm is a polynomial space algorithm (in our standard Turing machine model) and polynomial time algorithm in the arithmetic model (see this question for a clarification).

Why do they restrict to polynomial TM space as opposed to polynomial TM time? (this came up here)

It seems strange for an algorithm that takes a number of TM steps unboundable by a polynomial to still be considered strongly-polynomial (provided it takes polynomial space and a number of arithmetic operations polynomial in the number of numbers in the input). Can it be shown that such an algorithm does not exist? Perhaps based on this argument: the number of arithmetic operations would not be polynomial, since under the arithmetic model every operation is an arithmetic operation (?).

[1] Grötschel, Martin; László Lovász, Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.

$\endgroup$
1
  • $\begingroup$ Not really an answer to you question, but you might be interested in this algorithm. It takes polynomially-many arithmetic operations, exponential memory, and (still arguably) polynomial time with regards to the input size (although not on the TM model, but on a RAM machine). According to the current definition, it can surely not qualify as a strongly-polynomial algorithm. But is this an example of an algorithm that you would like to qualify as strongly-polynomial? Inc $\endgroup$ Commented Jul 21, 2017 at 10:25

1 Answer 1

14
$\begingroup$

No, any strongly-polynomial time algorithm can be converted into a polynomial time algorithm on a TM by replacing the arithmetic operations with equivalent algorithms in the TM model. That is the whole point of strongly-polynomial vs weakly-polynomial.

When you've analysed algorithms in the past, you've probably assumed that your arithmetic operations (addition, multiplication, etc.) take unit time. This is the arithmetic model of computation, where a step is defined as one arithmetic operation and input size is the number of integers. In the TM model, this isn't true, as a step is defined as moving the head and input size is defined as the number of bits used to represent the input. Thus arithmetic operations take time proportional to the number of bits used to represent them.

The definition restricts to TM space because that's the only condition you need to convert a polynomial time algorithm in the arithmetic model to a polynomial time algorithm in the TM model. The algorithm is already polynomial time in the arithmetic model, so as long as it's space is bounded in the TM model then the rest of the algorithm is still polynomial time in the TM model. Think of it like this, when converting from the arithmetic model to the TM model, the only thing that can go wrong is the space. The numbers you produce need to be representable in a number of bits that is polynomial in the number of bits in the input. So long as that holds, the rest of the algorithm is still polynomial time in the TM model.

In the case where you can't bound the space of your algorithm, you can't guarantee anything about the time when converting between the two models. There exist algorithms that take polynomial time in the arithmetic model but not in the TM model, and vice versa. Drawing examples from wikipedia let's elaborate on this.

An algorithm that is polynomial in the arithmetic model but not the TM model Suppose given the integer $2^n$ we wish to compute $2^{2^n}$ by repeated squaring. The integer $2^n$ takes space proportional to $n$ (i.e. the bits used to represent it). However $2^{2^n}$ takes space proportional to $2^n$, which is exponential in the size of the input. In the arithmetic model this algorithm is clearly polynomial since we perform $O(n)$ multiplications assuming each takes unit time which is polynomial in the input size. However the resulting value is exponential in the size of the input, so in the TM model this would take exponential time simply to write the bits necessary to store the result. Note that if we could bound the space of the algorithm, then we can guarantee that it is polynomial in the TM model as well.

An algorithm that is polynomial in the TM model but not the arithmetic model The standard GCD algorithm is one such example. Given two integers $a,b$ computing $gcd(a,b)$ takes $O((\log(a)+\log(b))^2)$ steps which is polynomial in the size of the input $\log(a)+\log(b)$. However in the arithmetic model the size of the input is just two integers and we can't bound the number of steps of the algorithm since it depends on the magnitude of $a$ and $b$.

Notice that the last example does not contradict the definition of strongly-polynomial. Strongly-polynomial doesn't say anything about algorithms that are polynomial in the TM model, it's only defined in the arithmetic model. If an algorithm is polynomial time in the arithmetic model and also happens to use space bounded in the size of input in the TM model, then it is strongly-polynomial.

$\endgroup$
2
  • 2
    $\begingroup$ Thank you. I see that the condition works, but why require poly-space instead of poly-TM time? If the answer is NO, the definition of SP could be simplified to "poly-arith-time + poly-TM-time". Why isn't it? $\endgroup$
    – alexei
    Commented Dec 22, 2012 at 22:33
  • 1
    $\begingroup$ "That is the whole point of strongly-polynomial vs weakly-polynomial." I don't think so. Weakly polynomial algorithms are also polynomial in the TM model. $\endgroup$
    – xskxzr
    Commented Feb 26, 2020 at 1:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.