3
$\begingroup$

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?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ @ged: Do you know why, informally, should one conjecture that gcd is specifically in NC? $\endgroup$
    – Łukasz Grabowski
    Nov 5, 2010 at 17:26
  • $\begingroup$ @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! $\endgroup$
    – ged
    Nov 9, 2010 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.