Welcome to MathOverflow

Question

5

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?

edited Feb 22 at 11:14

Sam Nead
5,637●12●27

asked Feb 22 at 8:58

unknown (google)
1,029●4●11

2

See cstheory.stackexchange.com/questions/2708/… – Zsbán Ambrus Feb 22 at 9:47

3

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/…). 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 at 12:17

1

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 at 16:59

1

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 at 12:37

1

... 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 at 12:41

show 3 more comments

Is integer GCD in NC?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.