3 added 149 characters in body

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)

2 edited tags
1

# Domination in Nice Lattices

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!