# Pick matrices such that each partial sum is positive

There is a sequence of $n$ sets, each set contains a constant number of constant-size vectors, e.g:

• $\{M_{1,1},M_{1,2},M_{1,3},M_{1,4}\}$
• $\{M_{2,1},M_{2,2},M_{2,3},M_{2,4}\}$
• ...
• $\{M_{n,1},M_{n,2},M_{n,3},M_{n,4}\}$

The task is to pick, from each set, a single vector, such that the sum of vectors and all the partial sums have no negative elements, i.e, select $i1,i2,...,in$ such that the following vectors:

• $M_{1,i1}$,
• $M_{1,i1} + M_{2,i2}$,
• $M_{1,i1} + M_{2,i2} + M_{3,i3}$,
• ...

have only non-negative elements.

• If you replace your matrices by vectors, the problem remains exactly the same. – xavierm02 Jan 12 '17 at 16:39
• @xavierm02 you are right, and it looks better with vectors. – Erel Segal-Halevi Jan 12 '17 at 16:56
• It's NP-complete. NP is easy. NP-hard because you can reduce $4-SAT$ to it. – xavierm02 Jan 12 '17 at 16:57

I'll represent you problem as:

Let $S_1, \dots, S_n$ be sets of $p$ vectors of size $d$. Find a vector $v_i$ in each $S_i$ so that for every $k\le n$, $\displaystyle \sum\limits_{0\le i \le k}v_i$ has only non-negative coordinates.

Prop: This problem is in NP.

Proof: Once we have the set of indices / vectors, it's easy to check that they work in polynomial time.

Prop: For $d\ge 2$ constant and $p\ge 2$ constant, the problem (where $n$ is not bounded) is NP-hard.

Proof: We take an instance of the subset-sum problem, which is NP-hard. We have integers $i_1, \dots, i_n$. We define $M=|i_1|+\dots + |i_n|$.

We take $S_0=\{[M,M]\}$. For $1\le k\le n$, $S_k=\{[i_k, -i_k],[0, 0]\}$ and $S_{n+1}=\{[-|M|, -|M|]\}$.

All the partial sums will clearly be $\ge 0$ except maybe the last one. The last one will be $\ge 0$ iff $\sum i_k\ge 0$ and $\sum -i_k\ge 0$, i.e. iff $\sum i_k = 0$. So there is a solution iff the subset sum instance has one.

The following is a weaker result but it's written so I leave it here.

Prop: This problem with $2n$ sets of $p$ vectors of size $2d$ is at least as hard as $CNF-SAT$ on $n$ clauses with $p$ literals per clause and $d$ variables.

Proof: Take a set $C_1,\dots, C_n$ of clauses on $d$ variables, with $p$ literals per clause. $C_i=l_{i,1}\lor \dots \lor l_{i,p}$.

We write $v_k$ for the $k$th variable. To a positive literal $l_{i,j}=v_k$, we associate the vector $\phi(v_k)$ of dimension $2d$ that has a $1$ at the $k$th position and $0$s everywhere else. To a negative literal $l_{i,j}=\lnot v_j$ we associate the vector $\phi(v_k)$ of dimension $2d$ with a $1$ in $d+k$th position and zeros everywhere else.

Now, for $1\le k \le n$, we set $S_i=\{n\phi(v_k),n\phi(\lnot v_k)\}$ (and we add some useless vectors with big negative values if you really want the set to have size $p$). For $1\le i\le n$, we set $S_{n+k}=\{-\phi(l_{i,j}) / j\in\{1,\dots,n\}\}$.

The idea is the following. In the first $n$ coordinates, we store how many times we can use each of the variable, and in the next $n$ coordinates, we store how many times we can use each of the negation of variables. Then, at the beginning, in the first $n$ sets, we pick for each variable if it's true or false (by adding $n$ to the number of times we can use the variable, or to the number of times we can use its negation). The last $n$ sets then use the variables / negations to make the clause true. To make a clause true, you need to make one literal true, and the true ltterals will be exactly those for which the corresponding coordinate is $>0$ so that you can subtract $1$ while remaining $\ge 0$. If you chose $v_k$ to be false, the corresponding coordinate will remain $0$ for the whole thing so if you try to use it, it will become $<0$. And we add $n$ at the beginning because since there are $n$ clauses, we won't subtract more than $n$.

Prop: For $p\ge 3$, the problem (where $d$ and $n$ are not bounded) is $NP$-hard.

Proof: The reduction given above reduces $3-SAT$ to it in polynomial time. And $3-SAT$ is NP-hard.