1
$\begingroup$

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.

Is anything known about this problem?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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