complexity of greatest common divisor (gcd)
This is a major open question in complexity theory: it is not known if GCDs can be computed in NC, and it is not known if computing GCDs is P-complete.  The best parallel algorithms do have sub-linear parallel running time, one such algorithm being due to Sorenson:


  J. Sorenson.  Two fast GCD algorithms.  Journal of Algorithms, 1994.


If I am not mistaken, it is not even known if one can decide whether two integers are relatively prime in NC.