34
$\begingroup$

Consider the following counting problem (or the associated decision problem): Given two positive integers encoded in binary, compute their greatest common divisor (gcd). What is the smallest complexity class this problem is contained in? Can you provide a reference?

In this question I am not primarily interested in asymptotic bounds on the running time, but rather in complexity classes. Is the problem in AC? Can it be proven not to lie in AC0? What are other complexity classes inside P that are of relevance here?

Improve this question
$\endgroup$
7
  • $\begingroup$ Well, clearly it is in FP by the Euclidean algorithm, but I don't really understand the rest of the question. AC, P and AC0 are all classes of decision problems, where as computing the GCD is not a decision problem. Is there some decision form of this problem you are interested in (i.e. is x = gcd(y,z)?), since you mention these classes? $\endgroup$
    – Joe Fitzsimons
    Nov 4, 2010 at 11:14
  • 3
    $\begingroup$ @Joe: My interpretation is that the asker is interested in whether the language {(x,y,i) | the i-th bit of gcd(x,y) is 1} is in NC, AC0, etc., but a clarification by the asker would be useful. $\endgroup$
    – Tsuyoshi Ito
    Nov 4, 2010 at 12:12
  • 1
    $\begingroup$ Yes, Tsuyoshi's phrasing of the decision problem is what I had in mind - sorry for the ambiguity. However, please do not focus on the complexity classes I suggested, as I simply do not know which complexity classes are of relevance here. I am curious about any nontrivial complexity class which is a subset of P (or FP, resp.) that contains gcd. $\endgroup$
    – Felix Breuer
    Nov 4, 2010 at 12:50
  • 1
    $\begingroup$ I'm curious about the case of gaussian integers. Quick google searches show ways to adapt the normal euclidean algorithm, but none of them discuss the relationship between the natural numbers and gaussian integers. Does any gcd algorithm over the natural numbers give us an algorithm over the gaussian integers with the same complexity? (I don't have an application, this is pure curiosity.) Also, are there efficient randomized algorithms for computing GCD with lower expected running times? $\endgroup$
    – Ross Snider
    Nov 6, 2010 at 17:41
  • 1
    $\begingroup$ Corrected link: mathoverflow.net/questions/44684/… . Thanks for the warning, Kaveh. $\endgroup$
    – Zsbán Ambrus
    May 15, 2013 at 8:11

3 Answers 3

Reset to default
45
$\begingroup$

This is a major open question in complexity theory: it is not known if GCDs can be computed in NC, and it is not known if computing GCDs is P-complete. The best parallel algorithms do have sub-linear parallel running time, one such algorithm being due to Sorenson:

J. Sorenson. Two fast GCD algorithms. Journal of Algorithms, 1994.

If I am not mistaken, it is not even known if one can decide whether two integers are relatively prime in NC.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you, that is what I wanted to know! However, if somebody knows other nontrivial subsets of P that are known to contain gcd, please let me know. $\endgroup$
    – Felix Breuer
    Nov 4, 2010 at 13:42
  • 15
    $\begingroup$ Testing if two integers are relatively prime is also open according to this reference: Limits to parallel computation, page 231, problem B.5.7. $\endgroup$
    – Robin Kothari
    Nov 4, 2010 at 14:51
  • 4
    $\begingroup$ A very recent reference is: Sorenson, Jonathan P. “A randomized sublinear time parallel GCD algorithm for the EREW PRAM.” Information Processing Letters 110, no. 5 (February 2010): 198-201. linkinghub.elsevier.com/retrieve/pii/S0020019009003640. $\endgroup$
    – Felix Breuer
    Nov 4, 2010 at 15:20
7
$\begingroup$

Somewhat late in the day but the following paper by Allender, Saks, Shparlinski proves that (among other lower bounds) that GCD is not in $\mathsf{AC}^0$ or $\mathsf{AC}^0[p]$ for any prime $p$.

Improve this answer
$\endgroup$
1
3
$\begingroup$

This paper, published in 2007, says that integer GCD is in NC.

Edit: The assertion is probably false. Check the comments.

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ The paper was never published, it was only posted on the author’s website. Moreover, the author himself does not seem to believe his 2007 paper is correct, as he lists the problem as open in his later papers (cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci09.pdf). $\endgroup$
    – Emil Jeřábek
    Sep 5, 2013 at 13:21
  • $\begingroup$ Did not know that. Thanks for pointing it out. $\endgroup$
    – Apoorv Gupta
    Sep 5, 2013 at 22:05
  • 1
    $\begingroup$ I don't think this kind of answers should be downvoted. $\endgroup$
    – Alessandro Cosentino
    Sep 5, 2013 at 22:16

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.