Approximating Good Simultaneous Diophantine Approximations is almost NP-hard

Given a real vector ff=(ff1 ; : : : ; ff d ) and a real number " ? 0 a good Diophantine approximation to ff is a number Q such that kQff mod Zk1 ", where k \Delta k1 denotes the `1-norm kxk1 := max 1id jx i j for x = (x1 ; : : : ; xd ). Lagarias [12] proved the NP-completeness of the corresponding decision problem, i.e., given a vector ff 2 Q d , a rational number " ? 0 and a number N 2 N+ , decide whether there exists a number Q with 1 Q N and kQff mod Zk1 ". We prove that, unless NP ` DTIME(n poly(log n) ), there exists no polynomial -time algorithm which computes on inputs ff 2 Q d and N 2 N+ a number Q with 1 Q 2 log 0:5\Gammafl d N and kQ ff mod Zk1 2 log 0:5\Gammafl d min 1qN jjqff mod Zk1 ; where fl is an arbitrary small positive constant. To put it in other words, it is almost NP--hard to approximate a minimum good Diophantine approximation to ff in polynomial-time within a factor 2 log 0:5\Gammafl d for an arbitrary small positive const.