Planar Integer Linear Programming is NC Equivalent to Euclidean GCD
David F. Shallcross, Victor Ya. Pan, Yu Lin-Kriz · SIAM Journal on Computing · 1998
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 computational problem was reduced in NC to the former one by Deng [Mathematical Programming: Complexity and Application, Ph.D. dissertation, Stanford University, Stanford, CA, 1989; Proc. ACM Symp. on Parallel Algorithms and Architectures, 1989,pp. 110--116]. We now prove the converse NC-reduction.