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
    
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? –  Joe Fitzsimons Nov 4 '10 at 11:14
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  
1  
Corrected link: mathoverflow.net/questions/44684/… . Thanks for the warning, Kaveh. –  Zsbán Ambrus May 15 '13 at 8:11

2 Answers 2

up vote 38 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
13  
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

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