Return to Answer

3. There are algorithms which run in polynomial time in the Turing machine model, but not in the arithmetic model. The Euclidean algorithm for computing the greatest common divisor of two integers is one example. If an algorithm runs in polynomial time in the Turing machine, will it run in polynomial time in the arithmetic model?

Polynomial TM running time does not imply polynomial arithmetic running time, nor vice-a-versa.

The issue in the above question lies in the definition of the running time that we are trying to bound. If we expand, we have to say: "...runs (or doesn't run) in the number of steps that is polynomial in the length of encoded input". The catch is that the "steps" and "length of encoded input" are defined differently for the two models.

• For a Turing Machine, the encoded input is taken as some concatenation of the binary representations of the input integers with separators. A step is an action of the TM head.

• For an arithmetic model, the length of encoded input is defined as the number of numbers occurring in the input. A step is an arithmetic operation.

1. "Polynomial time under TM, but not under AM"

Euclid's GCD is indeed an example. For $a,b, a>b$, input integers, regardless of the model the algorithm takes $O(\log b)$ iterations, with a division at each iteration.

• TM: Length of encoded input is then $l_{TM} = 2\log a + 1$ where $a$ is the larger of the two integers. The division in a TM takes $O(\log^2 a)$ steps. Hence, the total number of TM steps is $O(\log^2 a\log b)=O(l_{TM}^3)$ (conservatively speaking). That is, the polynomial $P_{TM}(l_{TM})=l_{TM}^3$ in the length of encoded input bounds the TM running time.

• AM: Length of encoded input is constant $l_{AM}=2$. The number of steps is equal to the number of divisions $O(\log b)$. Since the value of any polynomial $P(l_{AM})$ is constant, for any choice of $P(l_{AM})$ we can always find a problem instance that takes more divisions than $P(l_{AM})$. That is, we cannot bound the running time with a polynomial in the length of encoded input.

2. "Polynomial time under AM, but not under TM"

One example is the algorithm that computes $2^{2^n}$ using repeated-squaring where $n$ is given as input in unary encoding (and we treat each unary "tick" as an input number). For both models, input length is $n$ and we need $\log 2^n = n$ multiplications and each multiplication will eventually be multiplying $2^n$-bit numbers.

• AM: $P(n)=n$ is a polynomial bound on the number of arithmetic operations
• TM: $O(n2^{2n})$ steps, since each $2^n$-bit multiplication takes $O(2^{2n})$

Drawn from a reading of Wikipedia's primary source:

[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.

3. There are algorithms which run in polynomial time in the Turing machine model, but not in the arithmetic model. The Euclidean algorithm for computing the greatest common divisor of two integers is one example. If an algorithm runs in polynomial time in the Turing machine, will it run in polynomial time in the arithmetic model?

Polynomial TM running time does not imply polynomial arithmetic running time, nor vice-a-versa.

The issue in the above question lies in the definition of the running time that we are trying to bound. If we expand, we have to say: "...runs (or doesn't run) in the number of steps that is polynomial in the length of encoded input". The catch is that the "steps" and "length of encoded input" are defined differently for the two models.

• For a Turing Machine, the encoded input is taken as some concatenation of the binary representations of the input integers with separators. A step is an action of the TM head.

• For an arithmetic model, the length of encoded input is defined as the number of numbers occurring in the input. A step is an arithmetic operation.

1. "Polynomial time under TM, but not under AM"

Euclid's GCD is indeed an example. For $a,b, a>b$, input integers, regardless of the model the algorithm takes $O(\log b)$ iterations, with a division at each iteration.

• TM: Length of encoded input is then $l_{TM} = 2\log a + 1$ where $a$ is the larger of the two integers. The division in a TM takes $O(\log^2 a)$ steps. Hence, the total number of TM steps is $O(\log^2 a\log b)=O(l_{TM}^3)$ (conservatively speaking). That is, the polynomial $P_{TM}(l_{TM})=l_{TM}^3$ in the length of encoded input bounds the TM running time.

• AM: Length of encoded input is constant $l_{AM}=2$. The number of steps is equal to the number of divisions $O(\log b)$. Since the value of any polynomial $P(l_{AM})$ is constant, for any choice of $P(l_{AM})$ we can always find a problem instance that takes more divisions than $P(l_{AM})$. That is, we cannot bound the running time with a polynomial in the length of encoded input.

2. "Polynomial time under AM, but not under TM"

One example is the algorithm that computes $2^{2^n}$ using repeated-squaring where $n$ is given as input in unary encoding (and we treat each unary "tick" as an input number). For both models, input length is $n$ and we need $\log 2^n = n$ multiplications and each multiplication will eventually be multiplying $2^n$-bit numbers.

• AM: $P(n)=n$ is a polynomial bound on the number of arithmetic operations
• TM: $O(n2^{2n})$ steps, since each $2^n$-bit multiplication takes $O(2^{2n})$

Drawn from a reading of Wikipedia's primary source (and corrected Wikipedia accordingly):

[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.

3. There are algorithms which run in polynomial time in the Turing machine model, but not in the arithmetic model. The Euclidean algorithm for computing the greatest common divisor of two integers is one example.

The issue in the above question lies in the definition of the running time that we are trying to bound. If we expand, we have to say: "...runs (or doesn't run) in the number of steps that is polynomial in the length of encoded input". The catch is that the "steps" and "length of encoded input" are defined differently for the two models.

• For a Turing Machine, the encoded input is taken as some concatenation of the binary representations of the input integers with separators. Its length is then $l_{TM} = 2\log a + 1$ where $a$ is the larger of the two integers. A step is a action of the TM head.

• For an arithmetic model, the length of encoded input is defined as the number of numbers occurring in the input. For the Euclid's GCD this length is constant $l_{AM}=2$. A step is an arithmetic operation.

For $a,b, a>b$, input integers, the algorithm takes $O(\log b)$ iterations, with a division at each iteration.

• The division in a TM takes $O(\log^2 a)$ steps. Hence, the total number of TM steps is $O(\log^2 a\log b)=O(l_{TM}^3)$ (conservatively speaking). That is, the polynomial $P_{TM}(l_{TM})=l_{TM}^3$ in the length of encoded input bounds the TM running time.

• Under arithmetic model the number of steps is equal to the number of divisions $O(\log b)$. Since the value of any polynomial $P(l_{AM})$ is constant, for any choice of $P(l_{AM})$ we can always find a problem instance that takes more divisions than $P(l_{AM})$. That is, we cannot bound the running time with a polynomial in the length of encoded input.

If an algorithm runs in polynomial time in the Turing machine, will it run in polynomial time in the arithmetic model?

Repeated-squaring with a unary-encoded exponent as input is one example which runs in polynomial time under arithmetic model, but in exponential time under TM, since multiplication is no longer $O(1)$. E.g. given as input $n$ encoded as unary, to compute $2^{2^n}$, we need $\log 2^n = n$ multiplications, but each multiplication will eventually be multiplying $2^n$-bit numbers, which takes $O(2^{2n})$ TM-steps. Note that if the input exponent were binary-encoded, then the $n$ multiplications would be an exponential in the size of input.

Putting the two examples together, polynomial TM running time does not imply polynomial arithmetic running time, nor vice-a-versa.

3. There are algorithms which run in polynomial time in the Turing machine model, but not in the arithmetic model. The Euclidean algorithm for computing the greatest common divisor of two integers is one example. If an algorithm runs in polynomial time in the Turing machine, will it run in polynomial time in the arithmetic model?

Polynomial TM running time does not imply polynomial arithmetic running time, nor vice-a-versa.

The issue in the above question lies in the definition of the running time that we are trying to bound. If we expand, we have to say: "...runs (or doesn't run) in the number of steps that is polynomial in the length of encoded input". The catch is that the "steps" and "length of encoded input" are defined differently for the two models.

• For a Turing Machine, the encoded input is taken as some concatenation of the binary representations of the input integers with separators. A step is an action of the TM head.

• For an arithmetic model, the length of encoded input is defined as the number of numbers occurring in the input. A step is an arithmetic operation.

1. "Polynomial time under TM, but not under AM"

Euclid's GCD is indeed an example. For $a,b, a>b$, input integers, regardless of the model the algorithm takes $O(\log b)$ iterations, with a division at each iteration.

• TM: Length of encoded input is then $l_{TM} = 2\log a + 1$ where $a$ is the larger of the two integers. The division in a TM takes $O(\log^2 a)$ steps. Hence, the total number of TM steps is $O(\log^2 a\log b)=O(l_{TM}^3)$ (conservatively speaking). That is, the polynomial $P_{TM}(l_{TM})=l_{TM}^3$ in the length of encoded input bounds the TM running time.

• AM: Length of encoded input is constant $l_{AM}=2$. The number of steps is equal to the number of divisions $O(\log b)$. Since the value of any polynomial $P(l_{AM})$ is constant, for any choice of $P(l_{AM})$ we can always find a problem instance that takes more divisions than $P(l_{AM})$. That is, we cannot bound the running time with a polynomial in the length of encoded input.

2. "Polynomial time under AM, but not under TM"

One example is the algorithm that computes $2^{2^n}$ using repeated-squaring where $n$ is given as input in unary encoding (and we treat each unary "tick" as an input number). For both models, input length is $n$ and we need $\log 2^n = n$ multiplications and each multiplication will eventually be multiplying $2^n$-bit numbers.

• AM: $P(n)=n$ is a polynomial bound on the number of arithmetic operations
• TM: $O(n2^{2n})$ steps, since each $2^n$-bit multiplication takes $O(2^{2n})$

3. There are algorithms which run in polynomial time in the Turing machine model, but not in the arithmetic model. The Euclidean algorithm for computing the greatest common divisor of two integers is one example.

The Euclidean GCD algorithm runs in time polynomial in the number of bits of the input under both Turing machine and arithmetic model. For $a,b, a>b$, input integers, it takes $O(\log b)$ steps, with a division at each step. The division under arithmetic is $O(1)$ and under TM $O(\log^2 a)$. In either case, the total time is $O(\log a)$, polynomial in the number of bits.

NOTE: Wiki seems wrong on this point, as far as I understand, and others in the talk page have pointed it out as well. (Coincidentally, I was reading it too at about the same time this question was posted.)

If an algorithm runs in polynomial time in the Turing machine, will it run in polynomial time in the arithmetic model?

Repeated-squaring with a unary-encoded exponent as input is one example which runs in polynomial time under arithmetic model, but in exponential time under TM, since multiplication is no longer $O(1)$. E.g. given as input $n$ encoded as unary, to compute $2^{2^n}$, we need $\log 2^n = n$ multiplications, but each multiplication will eventually be multiplying $2^n$-bit numbers, which takes $O(2^{2n})$ TM-steps. Note that if the input exponent were binary-encoded, then the $n$ multiplications would be an exponential in the size of input.

As far as I can tell, if an algorithm runs in polynomial time on a TM, it has to run in polynomial time under arithmetic model since the number of steps can only be smaller.

3. There are algorithms which run in polynomial time in the Turing machine model, but not in the arithmetic model. The Euclidean algorithm for computing the greatest common divisor of two integers is one example.

The issue in the above question lies in the definition of the running time that we are trying to bound. If we expand, we have to say: "...runs (or doesn't run) in the number of steps that is polynomial in the length of encoded input". The catch is that the "steps" and "length of encoded input" are defined differently for the two models.

• For a Turing Machine, the encoded input is taken as some concatenation of the binary representations of the input integers with separators. Its length is then $l_{TM} = 2\log a + 1$ where $a$ is the larger of the two integers. A step is a action of the TM head.

• For an arithmetic model, the length of encoded input is defined as the number of numbers occurring in the input. For the Euclid's GCD this length is constant $l_{AM}=2$. A step is an arithmetic operation.

For $a,b, a>b$, input integers, the algorithm takes $O(\log b)$ iterations, with a division at each iteration.

• The division in a TM takes $O(\log^2 a)$ steps. Hence, the total number of TM steps is $O(\log^2 a\log b)=O(l_{TM}^3)$ (conservatively speaking). That is, the polynomial $P_{TM}(l_{TM})=l_{TM}^3$ in the length of encoded input bounds the TM running time.

• Under arithmetic model the number of steps is equal to the number of divisions $O(\log b)$. Since the value of any polynomial $P(l_{AM})$ is constant, for any choice of $P(l_{AM})$ we can always find a problem instance that takes more divisions than $P(l_{AM})$. That is, we cannot bound the running time with a polynomial in the length of encoded input.

If an algorithm runs in polynomial time in the Turing machine, will it run in polynomial time in the arithmetic model?

Repeated-squaring with a unary-encoded exponent as input is one example which runs in polynomial time under arithmetic model, but in exponential time under TM, since multiplication is no longer $O(1)$. E.g. given as input $n$ encoded as unary, to compute $2^{2^n}$, we need $\log 2^n = n$ multiplications, but each multiplication will eventually be multiplying $2^n$-bit numbers, which takes $O(2^{2n})$ TM-steps. Note that if the input exponent were binary-encoded, then the $n$ multiplications would be an exponential in the size of input.

Putting the two examples together, polynomial TM running time does not imply polynomial arithmetic running time, nor vice-a-versa.

Drawn from a reading of Wikipedia's primary source:

[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.