Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. 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$? In $AC^1$? Can it be proven not to lie in $AC^0$? What are other complexity classes inside $P$ that are of relevance here?

share|improve this question
    
I don't know about the complexity classes, but I think this is the state of the art for gcd computation: ams.org/journals/mcom/2008-77-261/S0025-5718-07-02017-0/…. –  Hans Lundmark Nov 3 '10 at 19:42
1  
(a) There is a related MO post (which does not answer your question): mathoverflow.net/questions/25055/… ; (b) This question would be seen by more complexity experts at cstheory.stackexchange.com . –  Joseph O'Rourke Nov 3 '10 at 21:03
add comment

1 Answer

up vote 2 down vote accepted

I cross-posted this question on stackexchange and John Watrous posted an answer. The gist was that it is not known whether gcd is in NC or P-complete. See, e.g., "J. Sorenson. Two fast GCD algorithms. Journal of Algorithms, 1994."

share|improve this answer
    
@ged: Do you know why, informally, should one conjecture that gcd is specifically in NC? –  Łukasz Grabowski Nov 5 '10 at 17:26
    
@Lukasz: I guess the main reason is that NC is one of the most well-known subsets of P. Another reason may be the ongoing quest for parallel gcd algorithms. However, if you know a different subset of P that you think is a more likely candidate, please let me know! –  ged Nov 9 '10 at 10:39
add comment

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.