Focus on a given row of the matrix, say Ai, and solve Ai.x = bi. The integer solutions form a lattice in n space. This occurs m times over, for each row in the matrix, hence we are taking the intersection of these lattices, giving a coarser lattice in n space.
In 3 space, which is all we can conveniently visualize, imagine a plane cutting through the first octant at an angle, just above the origin. The plane is dotted with a periodic pattern, the points of the lower dimensional lattice. Is there a lattice point in the first octant? Is there a lattice point whose coordinates are all nonnegative? This is an np complete problem.
Notice that this is a special case of the previous theorem. Augment the equations with inequalities that keep each coordinate ≥ 0. This gives a system of equations and inequalities that is np. But this is a restricted version of the aforementioned problem; is it still np hard?
Given an instance of 3-sat, reserve an entry in x for each boolean variable and its negation, as we did before. If z is such a variable, set z + ~z = 1. Thus z is true or false, and ~z is the opposite. If a clause is x|y|z, Bring in three more variables, which I will call u v and w. Write the equation x+y+z - (u+2v+3w) = 0. Here u indicates exactly one of the three atoms in the clause is true, v says two are true, and w indicates all three are true. Write another equation u+v+w = 1 to force exactly one of these three variables to be true. The integer solutions form a lattice, and one of these lattice points is nonnegative, in fact its coordinates are all 0 or 1, iff the boolean expression can be satisfied.
Start with a matrix equation A*x = b, which is a special case of the theorem discussed in the previous section. This is an np problem. If there is an integer solution, an ntm will find it in polynomial time, and the solution is not that large, relative to A and b. Measure its distance to 0, using any of the three metrics, and (nondeterministically) look for integer solutions that are closer to 0. Use binary search to home in on a solution that is closest to 0. Therefore, finding a closest lattice point is np.
Now let's show the problem is np complete, starting with the manhatan metric. Encode 3-sat as a system of equations, as we did above. Every lattice point, i.e. every integer solution, has at least n nonzero coordinates, where n is the sum of the clauses and variables in 3-sat. Each of these contributes at least 1, hence the smallest possible distance is n. A boolean solution has a distance of n, and if the distance is n, each boolean variable is 1 or 0, and each clause is satisfied. The closest point has metric n iff it is a solution to the boolean expression, and "closest lattice point" is np complete.
A similar proof holds for the euclidean metric. Ignore the square root, and minimize the sum of the squares of the coordinates. At least n coordinates are nonzero, with minimum values of 1, giving a total of n. Any deviation gives a larger metric. Hence the closest lattice point determines satisfiability.
Finally consider the max metric. A solution to 3-sat has distance 1 from the origin. Conversely, if a lattice point has distance 1 from the origin then exactly one of x or ~x is 1 and the other is 0 as before. Unfortunately one of u, v, or w could be -1 while the others equal 1. When w = -1 the corresponding clause fails via x+y+z - (1+2-3) = 0. To prevent this, add a variable q with w-v-u-q = 0. In a 3-sat solution q = ±1, which does not increase the distance from the origin. However, with w = -1, q = -3, and the lattice point is too far away. Once again the closest lattice point determines satisfiability.