7
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ See cstheory.stackexchange.com/questions/2708/… $\endgroup$
    – Zsbán Ambrus
    Commented Feb 22, 2013 at 9:47
  • 3
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Feb 22, 2013 at 12:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Feb 22, 2013 at 16:59
  • 1
    $\begingroup$ 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, ... $\endgroup$
    – Emil Jeřábek
    Commented Feb 24, 2013 at 12:37
  • 1
    $\begingroup$ ... 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}$. $\endgroup$
    – Emil Jeřábek
    Commented Feb 24, 2013 at 12:41

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .