Paper Info
Title
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.
Year
DOI
Venue
1985
10.1137/0214016
SIAM Journal on Computing
Keywords
Field
DocType
simultaneous diophantine approximation problem,computational complexity,algorithm design and analysis,np complete problem,rational number,cryptography,polynomials,approximation algorithms,accuracy,public key cryptography,lattices,silicon,diophantine approximation,linear programming,satisfiability
Approximation algorithm,Discrete mathematics,Rational number,Uniform norm,Combinatorics,Polynomial,Real number,Fraction (mathematics),Mathematics,Computational complexity theory,Diophantine approximation
Journal
Volume
Issue
ISSN
14
1
0097-5397
Citations 
PageRank 
References 
91
24.33
4
Authors
1
Name
Order
Citations
PageRank
J. C. Lagarias1563235.61