I don't understand why GCD is not Strongly Polynomial Time?

Can you explain in an example, why the storage size cannot be Polynomial Bounded?

So is GCD in the Complexity Class P?

  • 1
    $\begingroup$ What don't you understand? What are your thoughts? Have you tried applying the definition? Where have you looked? We expect you to do a significant amount of research before asking -- if the answer is explained in a natural place on Wikipedia or follows directly from the definition, you might want to do more research before asking. $\endgroup$ – D.W. Feb 13 '15 at 23:46

The GCD can be computed in polynomial time. Strongly Polynomial is a much more restrictive classification. Taking the definition from here:

An algorithm runs in strongly polynomial time if

  • 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

  • the space used by the algorithm is bounded by a polynomial in the size of the input.

The input to GCD is two integers. Thus, in order to be solvable in strongly polynomial time, GCD would need to be solvable with a constant number of aritmethic operations since the input size is constant.


As Wikipedia mentions, the reason that the Euclidean algorithm for GCD doesn't run in strongly polynomial time is that the number of arithmetic operations is unbounded, although there are always only two inputs. On the other hand, the running time is polynomial in the input size, and so the Euclidean algorithm runs in polynomial time. In particular, GCD is in FP (the class of functions computable in polynomial time).

  • $\begingroup$ but why do you measure the the arithmetic operations against the number of inputs and not against the input size like in the runtime? wouldn't it make much more sense to measure the arithmetic operations against the input size and the time against the number of elements? $\endgroup$ – testy Feb 13 '15 at 22:21
  • 1
    $\begingroup$ That's the definition of "strongly polynomial time". If you don't like it, don't use it. In some cases it makes sense - for example, for some reason people really care about whether a strongly polynomial time algorithm for linear programming exists. If you want to know why, you can ask a separate question. $\endgroup$ – Yuval Filmus Feb 13 '15 at 22:23
  • $\begingroup$ and isn't the number of arithmetics operation and the running time not the same? or whats the difference between them? $\endgroup$ – testy Feb 13 '15 at 22:26
  • $\begingroup$ There could or could not be a difference, depending on your computation model, but in this case it's not important. The number of arithmetic operations is polynomial in the input size but not polynomial in the number of inputs. That's the problem. $\endgroup$ – Yuval Filmus Feb 13 '15 at 22:28
  • 1
    $\begingroup$ In this game, you're counting each arithmetic operation as one unit. So addition is trivially strongly polynomial, since it's part of your basic repertoire. If you have a strongly polynomial algorithm then you can apply to numbers in any field, for example, without any penalties beyond that of actually performing the arithmetic. For example, you could work in an algebraic number field, something which might be impossible in a weakly polynomial algorithm. $\endgroup$ – Yuval Filmus Feb 14 '15 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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