7
$\begingroup$

The traditional problem of simultaneous diophantine approximation is: Given a set of rational numbers $g_1,\ldots,g_d$, an integer $N$, and a rational $\gamma>0$, is there an integer $W$ with $1\le W\le N$ such that $$\forall i\ \min_{n\in \mathbb{Z}} |Wg_i - n| < \gamma\ ?$$ This problem was shown to be NP-complete by Lagarias. ("The computational complexity of simultaneous diophantine approximation problems", SIAM J. Comput., 14(1):196–209, Feb. 1985.)

With the same inputs, we can also ask: Is there $W$ such that $$\forall i\ \min_{n\in \mathbb{Z}} |g_i - n/W|<\gamma\ ?$$

Is it still an NP-complete problem to find a good diophantine approximation in this sense? Thanks!

Improve this question
$\endgroup$
5
  • $\begingroup$ The question does not make sense as written: NP is a class of decision problems, not search problems, and one cannot represent arbitrary reals by finite strings as there are uncountably many. The problem shown NP-complete by Lagarias is to determine whether there exists such a $W$, and it has rational $\alpha,\gamma$ as input. Is this what you want? $\endgroup$
    – Emil Jeřábek
    Commented Oct 1, 2014 at 16:15
  • $\begingroup$ @EmilJeřábek: you are right, sorry, I was not precise enough. I've fixed the question. $\endgroup$
    – Krisztián Németh
    Commented Oct 1, 2014 at 18:46
  • $\begingroup$ OK. I haven’t studied Lagarias paper in detail, but my gut feeling is that it should still be NP-complete. Did you try to play a bit with the reduction in his argument to see whether it might yield this? (It might even be simpler than the original.) $\endgroup$
    – Emil Jeřábek
    Commented Oct 1, 2014 at 19:00
  • $\begingroup$ To be honest, I'm "just an engineer", but my mathematician friends tried to do so, but they gave up, the proof was too complicated, they said... $\endgroup$
    – Krisztián Németh
    Commented Oct 3, 2014 at 8:07
  • $\begingroup$ Related: rjlipton.wordpress.com/2009/08/01/… $\endgroup$
    – domotorp
    Commented Oct 9, 2014 at 19:04

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .