The Computational Complexity of Simultaneous Diophantine Approximation Problems

Simultaneous Diophantine approximation in d dimensions deals with the approximation of a vector α = (α ₁ , ⋯ ,α d ) of d real numbers by vectors of rational numbers all having the same denominator. This paper considers the computational complexity of algorithms to find good simultaneous approximations to a given vector α of d rational numbers. We measure the goodness of an approximation using the sup norm. We show that a result of H. W. Lenstra, Jr. produces polynomial-time algorithms to find sup norm best approximations to a given vector α when the dimension d is fixed. We show that a recent algorithm of A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovasz to find short vectors in an integral lattice can be used to find a good approximation to a given vector α in d dimensions with a denominator Q^ * satisfying 1 Q^ * 2d/2 N which is within a factor √5d 2(d + 1)/2 of the best approximation with denominator Q with 1 Q N. This algorithm runs in time polynomial in the input size, independent of the dimension d. We also prove complementary results showing that certain natural simultaneous Diophantine approximation problems are NP-hard. We show that the problem of deciding whether a given vector α of rational numbers has a simultaneous approximation of specified accuracy with respect to the sup norm with denominator Q in a given interval 1 Q N is NP-complete. (Here the dimension d is allowed to vary.) We prove two other complexity results, which suggest that the problem of locating best (sup norm) simultaneous approximations is harder than this NP-complete problem.