The computational complexity of simultaneous Diophantine approximation problems

Abstract

Simultaneous Diophantine approximation in d dimensions deals with the approximation of a vector α = (α1, ..., α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 2d+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 prove results complementing these, showing 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.