0
$\begingroup$

Despite centuries of search extended $GCD$ is known to accommodate one algorithm which is the Euclidean algorithm (the solution through Integer Linear Programming which needs basis reduction goes through a step similar to Euclidean algorithm).

Is there evidence that extended $GCD$ might be in $TC^0$?

Improve this question
$\endgroup$
2
  • $\begingroup$ IIRC even just gcd (let alone extended gcd) is not known to be in NC, and TC0 is contained in NC1. So...what kind of evidence would you hope for? $\endgroup$
    – Joshua Grochow
    Commented May 30 at 18:13
  • $\begingroup$ GCD on two numbers seems to be a minimal non trivial operation on two numbers which is more complex than the TC^0 operation of multiplication of two numbers. $\endgroup$
    – Turbo
    Commented May 30 at 18:17

0

Reset to default

Your Answer

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