Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)

share|improve this question
    
Trivial comment. If we take $v_1=(1,-1,0, \dots, 0), v_2=(0,1,-1,0, \dots, 0), \dots, v_{n-1}=(0, \dots, 1,-1)$, then the $\mathbb{Z}$-span of all the $v_i$'s is in fact all integer vectors whose coordinates sum to zero. –  Tony Huynh Feb 22 '11 at 14:53
    
Not-as-trivial comment: There are at most finitely many vectors y which are both nice and greater than x (the sum of whose components must be at most 0). This can be transformed into finding integer solutions to a system of linear inequalities; if the transform went the other way, I think it would show the problem to be NP-complete. Gerhard "Ask Me About System Design" Paseman, 2011.02.22 –  Gerhard Paseman Feb 22 '11 at 17:16
    
Of course, there is the brute force approach: if the sum of the coefficients of x is -r, try the O(r^(n-1)) nice vectors above x and see which are in the desired lattice. Gerhard "Is There A Better Way" Paseman, 2011.02.22 –  Gerhard Paseman Feb 22 '11 at 17:23
    
Yes, your comments are valid. Tony, more generally than what you state, the problem becomes poly-time solvable if all of the nonzero entries form a chain under division (e.g., all 1s, 2s, 6s, 30s...) –  Dave Pritchard Feb 24 '11 at 11:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.