MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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

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.