15
$\begingroup$

Consider the following problem:

Input: a hyperplane $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$, given by a vector $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ in standard binary representation.

Output: $\mathbf{x} \in \mathbb{Z}^n = \arg \min d( \mathbf{x}, H)$

In the above notation $d(\mathbf{x}, S)$ for $\mathbf{x} \in \mathbb{R}^n$ and $S \subseteq \mathbb{R}^n$ is defined as $d(\mathbf{x}, S) = \min_{\mathbf{y} \in S}{\|\mathbf{x} - \mathbf{y}}\|_2$, i.e. it's the natural euclidean distance between a set of points and a single point.

In words, we're given a hyperplane and we're looking for the point in the integer lattice that is closest to the hyperplane.

The question is:

What is the complexity of this problem?

Note that polynomial time here will mean polynomial in the bitsize of the input. As far as I can see the problem is interesting even in two dimensions. Then it's not hard to see that it's enough to consider only those solutions $(x_1, x_2)$ with $0\leq x_1 \leq |a_1|/\mathsf{gcd}(a_1, a_2)$ but that's superpolynomially many options.

A closely related problem is solving a linear diophantine equation, i.e. finding an $\mathbf{x} \in \mathbb{Z}^n$ such that $\mathbf{a}^T\mathbf{x} = b$ or determining that no such $\mathbf{x}$ exists. So, solving a linear diophantine equation is equivalent to determining whether there exists a solution of value 0 to the problem I defined above. A linear diophantine equation can be solved in polynomial time; in fact even systems of linear diophantine equations can be solved in polynomial time by computing the Smith normal form of the matrix $\mathbf{A}$ giving the system. There are polynomial time algorithms that compute the Smith normal form of an integer matrix, the first one given by Kannan and Bachem.

To get intuition about linear diophantine equations we can consider the two dimensional case again. Clearly, there is no exact solution if $\mathsf{gcd}(a_1, a_2)$ does not divide $b$. If it does divide $b$, then you can run the extended GCD algorithm to get two numbers $s$ and $t$ such that $a_1s + a_2t = \mathsf{gcd}(a_1, a_2)$ and set $x_1 = sb/\mathsf{gcd}(a_1, a_2)$ and $x_2 = tb/\mathsf{gcd}(a_1, a_2)$. Now you can see how the approximate version is different: when $\mathsf{gcd}(a_1, a_2)$ does not divide $b$, how do we find integers $x_1, x_2$ such that distance between $(x_1, x_2)$ and the line $a_1x_1 + a_2x_2 =b$ is minimized?

The problem to me sounds a little like the closest vector problem in lattices, but I do not see an obvious reduction from either problem to the other.

$\endgroup$
  • $\begingroup$ Does Approximating Good Simultaneous Diophantine Approximations Is Almost NP-Hard, C Rössner and J-P Seiffert, MFCS 96 answer your question? $\endgroup$ – Kai Dec 30 '11 at 8:06
  • $\begingroup$ no it does not: diophantine approximation is a different problem from solving a diophantine equation. in a diophantine approximation problem you're given $n$ real numbers and you want to multiply them all by a single integer $Q$ so that all of them are within $\epsilon$ from some integer. the issue there is finding the optimal tradeoff between the size of $Q$ and $\epsilon$. I do not see a relation between my problem and this one. $\endgroup$ – Sasho Nikolov Dec 30 '11 at 10:04
  • $\begingroup$ What's your input format? It seems as though if any two coordinate values of $\mathbf{a}$ are incommensurate then the minimum in question is zero (intersect with the appropriate 2-dimensional plane to get an equation of the form $sx+ty=w$ with $s$ and $t$ incommensurate, i.e. $\alpha \equiv \frac{s}{t}$ irrational, and then use the standard results on $\left\{n\alpha\right\}\pmod 1$ to show that the line passes arbitrarily close to lattice points. $\endgroup$ – Steven Stadnicki Feb 1 '12 at 19:47
  • $\begingroup$ In particular, this means that your 'min' should be an 'inf' (sine you're taking it over infinitely many points), and the problem of whether $\mathrm{inf}\ d(\mathbf{x},H)=0$ is distinct from the question of whether there exists some $\mathbf{x}$ with $d(\mathbf{x},H)=0$. This means the coefficients of $\mathbf{a}$ have to be rational numbers for the problem to have nontrivial solution, and then the problem seems to take on a very Euclidean form, closely coupled to multidimensional GCD algorithms. Am I missing something? $\endgroup$ – Steven Stadnicki Feb 1 '12 at 19:52
  • $\begingroup$ @StevenStadnicki right. you can assume $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ (I will add that to the question, I must have missed it). the input is given in standard binary representation. the question is interesting even when $n = 2$. then it's enough to consider all possible solutions $(x_1, x_2)$ with $x_1 \leq |a_1|/\mathsf{gcd}(a_1, a_2)$, but the bruteforce search will be superpolynomial in the binary representation of $a_1, a_2$. $\endgroup$ – Sasho Nikolov Feb 1 '12 at 20:15
5
+100
$\begingroup$

All right, having thought about it more I believe I have an explicit reduction from this problem to extended GCD; I'll explain it in the $n=2$ case, but I believe that it extends to arbitrary $n$. Note that this finds an $\mathbf{x}$ that minimizes the distance to the hyperplane, but not necessarily the smallest $\mathbf{x}$ (there are in fact infinitely many values that attain the same minimum distance) - I believe the latter problem is also feasible, but haven't given it any real thought yet. The algorithm is based on a few simple principles:

  • If $g=\mathrm{GCD}(a_1, a_2)$, then the set of values taken on by $\mathbf{a}\cdot\mathbf{x} = a_1 x_1 + a_2 x_2$ is precisely $\left\{0, \pm g, \pm 2g, \pm 3g, \ldots\right\}$; furthermore, values $x_1$ and $x_2$ with $a_1 x_1 + a_2 x_2 = g$ can be found efficiently (this is exactly the extended Euclidean algorithm).
  • The minimum distance from the hyperplane to a point on the lattice is the minimal distance from a point on the lattice to the hyperplane (obvious, but a useful inversion of the problem).
  • The distance from a given point $\mathbf{x}$ to the hyperplane $\mathbf{a}\cdot\mathbf{y} = b$ is proportional to $\left|\mathbf{a}\cdot\mathbf{x}-b\right|$ (specifically, it's $1/|\mathbf{a}|$ times this value - but since multiplying all distances by this value has no effect on the location of the minimum, we can ignore the normalizing factor).

This suggests the following procedure:

  • Compute $g=\mathrm{GCD}(a_1,a_2)$, along with $x^0_1, x^0_2$ such that $a_1x^0_1+a_2x^0_2 = g$.
  • Compute $r = \left\lfloor{b\over g}\right\rfloor$ and calculate $d =\min(b-rg, (r+1)g-b)$; $d$ is the (scaled) minimal distance from the lattice to the hyperplane. Let $s$ be either $r$ or $r+1$ ($=\left\lceil{b\over g}\right\rceil$, unless $b$ is a multiple of $g$) depending on which one attains the minimal distance.
  • Compute $x_1 = sx^0_1$ and $x_2 = s x^0_2$; then $\mathbf{a}\cdot\mathbf{x} = sg$ is the nearest multiple of $g$ to $b$, and thus $\left|\mathbf{a}\cdot\mathbf{x}-b\right|$ attains the minimum of this distance over all lattice points.

As far as I know, the exact same procedure should work correctly in arbitrary dimensions; the key is that the $n$-dimensional GCD still satisfies Bezout's identity, and so to find the minimum distance to a lattice point you only have to find the nearest multiple of $g$ to $b$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.