Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.
Call a lattice nice if it is of the form $\mathbb{Z}$-span({$v_1, v_2, \dotsc, v_m$}), where all $v_i$ are nice. (Note: the $v_i$ are not necessarily linearly independent so $m$ could be larger than the dimension; although WOLOG $m \le \tbinom{n}{2}$.)
Is the following decision problem in P?
- INPUT: a nice lattice and a vector $x \in \mathbb{Z}^n$
- QUESTION: does the lattice contain a $y$ such that $y_i \ge x_i$ for all $i=1, \dotsc, n$?
Motivation and background:
- in general lattices, the problem is NP-complete (via the unbounded knapsack problem)
- if this problem lies in P, one can solve an interesting more general problem
A possibly interesting partial result would be to demonstrate any useful structure for nice lattices!
(I posted a flow formulation of the problem on cstheory)
