New Hardness Results for Diophantine Approximation

We revisit

simultaneous Diophantine approximation

, a classical problem from the geometry of numbers which has many applications in algorithms and complexity. The input to the decision version of this problem consists of a rational vector

α

 ∈ ℚ

n

, an error bound

ε

and a denominator bound

N

 ∈ ℕ

 + 

. One has to decide whether there exists an integer, called the

denominator

Q

with 1 ≤ 

Q

 ≤ 

N

such that the distance of each number

Q

·

α

i

to its nearest integer is bounded by

ε

. Lagarias has shown that this problem is NP-complete and optimization versions have been shown to be hard to approximate within a factor

n

c

/ loglog

n

for some constant

c

 > 0. We strengthen the existing hardness results and show that the optimization problem of finding the

smallest denominator

Q

 ∈ ℕ

 + 

such that the distances of

Q

·

α

i

to the nearest integer are bounded by

ε

is hard to approximate within a factor 2

n

unless

${\textrm{P}} = {\rm NP}$

.

We then outline two further applications of this strengthening: We show that a directed version of Diophantine approximation is also hard to approximate. Furthermore we prove that the

mixing set

problem with arbitrary capacities is NP-hard. This solves an open problem raised by Conforti, Di Summa and Wolsey.