Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Wikipedia, in the page http://en.wikipedia.org/wiki/Greatest_common_divisor#Complexity mentions integer GCD is in NC by citing http://www.cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci07.pdf

In another place, http://en.wikipedia.org/wiki/NC_(complexity)#Problems_in_NC , it mentions "it is open whether integer GCD is in NC".

Which is correct?

share|improve this question
This is still an open problem. I don’t know what exactly happened with the Sedjelmaci 2007 unpublished paper, but he seems to have retracted the claim, as he mentions the problem as open in his later papers (lipn.univ-paris13.fr/~sedjelmaci/JDA08.pdf, cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci09.pdf). I’ve removed the claim from Wikipedia (added in January by an anon), as it clearly fails the reliable source criteria. –  Emil Jeřábek Feb 22 '13 at 12:17
Basically, the coefficients of a polynomial gcd can be expressed using determinants of submatrices of the Sylvester matrix, and determinants can be computed in NC. No such reduction to linear algebra is known in the case of integers. –  Emil Jeřábek Feb 22 '13 at 16:59
I can't say I understand how you want it to work: we are talking GCD in $\mathbb Q[x]$, which is only defined up to an arbitrary nonzero rational multiple, hence evaluating it at $b$ gives no information at all. (GCD in $\mathbb Z[x]$ is trivially as hard as GCD in $\mathbb Z$, by considering constant polynomials.) In any case, the best you can hope for with such a strategy is to show that integer GCD cannot be computed by a particular kind of NC algorithms. It says nothing about whether it can be computed by a completely different NC algorithm. Note that if integer GCD is not in NC, ... –  Emil Jeřábek Feb 24 '13 at 12:37
... then in particular $\mathrm P\ne\mathrm{NC}$, which is a notorious open problem akin to $\mathrm P\ne\mathrm{NP}$. You are not going to prove this using a naive or simple method. A more realistic idea would be to show that integer GCD is P-hard, which would imply it is not in NC unless $\mathrm P=\mathrm{NC}$. –  Emil Jeřábek Feb 24 '13 at 12:41
show 3 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer


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

Browse other questions tagged or ask your own question.