7
$\begingroup$
  1. How is an arithmetic model defined?

    What relations are between it and Turing machine? Are they equivalent in some sense?

    Is it true that

    • in the arithmetic model of computation, the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a constant unit time step to perform, regardless of the sizes of the operands.

    • in the Turing machine, the time each operation takes will depends on the storage size of the operands?

    What is the point of having these two different computational models?

  2. Are there other models of computation distinct from the Turing machine and the arithmetic model?

  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?

  4. Is an algorithm running in polynomial storage space defined the same under the Turing machine and the arithmetic model?

Thanks and regards!

$\endgroup$
5
  • $\begingroup$ The Euclidean algorithm most certainly runs in polynomial time in the Turing machine model. You can easily show this by noting that you can easily perform subtraction in the Turing machine model, and order comparisons with the number 0, in polynomial time. $\endgroup$ Dec 17, 2012 at 15:14
  • $\begingroup$ @NieldeBeaudrap: Thanks! Can you also comment on the question in the reverse direction, and on the computational models? $\endgroup$
    – Tim
    Dec 17, 2012 at 15:29
  • $\begingroup$ Perhaps you should revise your question to remove the error, and also focus on just one of your questions. Have you done much reading of your own on the arithmetic model? That may answer many of your questions. $\endgroup$ Dec 17, 2012 at 15:35
  • $\begingroup$ @NieldeBeaudrap: Thanks! The error is corrected (it was copied from Wikipedia). I don't find things to read for the arithmetic model. Do you mind recommend some? $\endgroup$
    – Tim
    Dec 17, 2012 at 15:40
  • $\begingroup$ For arithmetic, they're definitely not in constant time if there's unlimited-precision integers. Usually they're modeled as constant time because in practice, they're done using the CPU 32/64 bit instructions which do happen in constant time. $\endgroup$
    – jmite
    Dec 21, 2012 at 23:56

2 Answers 2

10
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

2. Are there other models of computation distinct from the Turing machine and the arithmetic model?

  • Tag-systems (and their variations: 2-tag systems, cyclic tag systems, bi-tag systems)

All those models are Turing complete (and can simulate a Turing machine with only polynomial time slowdown). A lot of information can be found in Turlough Neary's thesis "Small universal Turing Machines"

$\endgroup$

Your Answer

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

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