PLANAR INTEGER LINEAR-PROGRAMMING IS NC EQUIVALENT TO EUCLIDEAN GCD

It is not known if planar integer linear programming is P-complete or if it is in NC, and the same can be said about the computation of the remainder sequence of the Euclidean algorithm applied to two integers. However, both computations are NC equivalent. The latter computationa l problem was reduced in NC to the former one by Deng [Mathematical Pr ogramming: Complexity and Application, Ph.D. dissertation, Stanford Un iversity, Stanford, CA, 1989; Proc. ACM Symp. on Parallel Algorithms a nd Architectures, 1989, pp. 110-116]. We now prove the converse NC-red uction.