Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
@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. –  Tsuyoshi Ito Nov 4 '10 at 12:12
1  
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. –  Felix Breuer Nov 4 '10 at 12:50
1  
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? –  Ross Snider Nov 6 '10 at 17:41
1  
1  
Corrected link: mathoverflow.net/questions/44684/… . Thanks for the warning, Kaveh. –  Zsbán Ambrus May 15 '13 at 8:11

3 Answers 3

up vote 42 down vote accepted

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.

share|improve this answer
    
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. –  Felix Breuer Nov 4 '10 at 13:42
14  
Testing if two integers are relatively prime is also open according to this reference: Limits to parallel computation, page 231, problem B.5.7. –  Robin Kothari Nov 4 '10 at 14:51
4  
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. –  Felix Breuer Nov 4 '10 at 15:20

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

share|improve this answer
    
Also see: cstheory.stackexchange.com/questions/8000/… –  SamiD Jan 5 at 16:30

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

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

share|improve this answer
4  
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). –  Emil Jeřábek Sep 5 '13 at 13:21
    
Did not know that. Thanks for pointing it out. –  Apoorv Gupta Sep 5 '13 at 22:05
1  
I don't think this kind of answers should be downvoted. –  Alessandro Cosentino Sep 5 '13 at 22:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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