Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I'm looking at the following problem:

Given $n$-dimensional vectors of natural numbers $v_1, \ldots, v_m$ and some input vector $u$, is $u$ a linear combination of the $v_i$'s with natural number coefficients?

i.e. are there some $t_1, \ldots, t_m \in \mathbb{N}$ where $u = t_1 v_1 + \ldots + t_m v_m$?

Obviously the real-number version of this problem can be solved using Gaussian elimination. I'm wondering, has the integer version of this problem been studied? What algorithms exist to solve it?

Note that this is using natural numbers, but not modular arithmetic, so this is somewhat separate from the Chinese Remainder Theorem and systems like that. Also, it seems related to Diophantine equations, but I'm wondering what has been done in the case where only non-negative integers are considered?

(For anyone interested, this is motivated by looking at whether a Parikh vector is in a linear set, as in Parikh's Theorem.

EDIT: In particular, I'm interested in an algorithm that could solve the problem using only natural number operations, avoiding going into the reals/floating point numbers.

share|improve this question
1  
Yes, the integer version (and various ring theoretic versions) have been studied. The integer version can be solved by Gaussian elimination. The natural number version is a different beast. My feeling is that it should be NP-complete. –  Thomas Klimpel May 29 at 16:34
    
How can it be NP-complete if it's solved by Gaussian elimination? I'm still interested in algorithms for it, even if it's an intractible problem. –  jmite May 29 at 17:26
    
Also note that in the problem I'm looking at, the system might be under-determined, i.e. $m < n$. Not sure how this changes it. –  jmite May 29 at 17:35
add comment

1 Answer 1

Your problem is NP-complete, by reduction from Subset Sum (it is in NP since the fact that everything is non-negative bounds the coefficients of the solution sufficiently well). Given an instance $S = \{s_1,\ldots,s_n\}, T$ of Subset Sum (is there a subset of $S$ summing to $T$?), we construct an instance $v_1,\ldots,v_{2n},u$ of your problem as follows. For each $1 \leq i \leq n$, we put $v_i$ to be the vector with two non-zero entries: $v_{i,i} = 1$ and $v_{i,n+1} = s_i$, and $v_{n+i}$ to be the vector with a unique non-zero entry $v_{n+i,i} = 1$. The target vector is $u=1,\ldots,1,T$. Each natural combination of $v_1,\ldots,v_{2n}$ equal to $1,\ldots,1,\ast$ must select exactly one of each of $v_i,v_{n+i}$, and so encodes a subset of $S$ whose sum is the value of the last component.

share|improve this answer
    
Interesting. Did you come up with this proof, or do you have a reference for it I could cite? Either way, thanks! –  jmite May 29 at 18:14
1  
@jmite I just came up with the proof, though I cannot rule out having seen it. –  Yuval Filmus May 29 at 18:14
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.