most recent 30 from http://mathoverflow.net 2013-05-26T09:09:15Z http://mathoverflow.net/feeds/question/56281 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56281/domination-in-nice-lattices Dave Pritchard 2011-02-22T13:28:37Z 2011-02-24T11:46:31Z

<p>Let an integer vector be <em>nice</em> 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.</p> <p>Call a lattice <em>nice</em> 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}$.)</p> <p>Is the following decision problem in P?</p> <ul> <li>INPUT: a nice lattice and a vector $x \in \mathbb{Z}^n$</li> <li>QUESTION: does the lattice contain a $y$ such that $y_i \ge x_i$ for all $i=1, \dotsc, n$?</li> </ul> <p>Motivation and background:</p> <ul> <li>in general lattices, the problem is NP-complete (via the unbounded knapsack problem)</li> <li>if this problem lies in P, one can solve an interesting more general problem</li> </ul> <p>A possibly interesting partial result would be to demonstrate any useful structure for nice lattices!</p> <p>(I posted a <a href="http://cstheory.stackexchange.com/questions/5119/quantized-unbounded-flow" rel="nofollow">flow formulation of the problem</a> on cstheory)</p>