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.
