This paper considers the computational complexity of algorithms to find good simultaneous approximations to a given vector of d rational numbers. Such problems have a number of important applications. The goodness of an approximation is measured by the sup norm.

After surveying the work of Lenstra, Lenstra, and Lovasz [1] on polynomial time algorithms, the author proves that certain natural simultaneous diophantine approximation problems are NP-hard. Two consequences are derived which suggest that the problem of locating best simultaneous approximations is computationally harder than that of locating good simultaneous approximations. The majority of the paper consists of proofs of these results. Two conjectures for further work are also presented.