<p><em>EDIT: Merged the two answers.</em></p>

<p>Here's the problem statement:</p>

<p><em>The input is <span class="math-container">$(V, \mathbf b, \ell)$</span>, where <span class="math-container">$V=\{x_1,x_2,\ldots,x_n\}$</span> with each <span class="math-container">$x_i\in\{0,1\}^d$</span> (where <span class="math-container">$d$</span> is constant), vector <span class="math-container">$\textbf{b}=(b_1,b_2,\ldots,b_d)\in \mathbb{Z}_+^d$</span>, and <span class="math-container">$\ell$</span> is an integer.
The problem is to decide whether <span class="math-container">$V$</span> can be partitioned into <span class="math-container">$\ell$</span> parts <span class="math-container">$V_1,V_2,\ldots,V_\ell$</span> such that <span class="math-container">$\forall~j,\sum_{x_i\in V_j} x_i \leq \textbf{b}$</span>.</em></p>

<p><strong>Lemma 1.</strong> <em>The problem (with <span class="math-container">$d=O(1)$</span>) reduces to a sparse language, so is not NP-hard unless P=NP.</em></p>

<p><strong>Lemma 2.</strong> <em>For <span class="math-container">$d=O(1)$</span> and <span class="math-container">$\ell=O(1)$</span>, the problem can be solved in polynomial time via dynamic programming (EDIT: or an ILP of constant dimension).</em></p>

<p><strong>Lemma 3.</strong> <em>For <span class="math-container">$d=O(1)$</span> and <span class="math-container">$\max_j b_j=O(1)$</span>, the problem can be solved in linear time (in the real RAM model) via an ILP of constant dimension.</em></p>

<p>This leaves open the complexity of the case when <span class="math-container">$\ell$</span> and <span class="math-container">$\max_j b_j$</span> are both allowed to grow (while <span class="math-container">$d=O(1)$</span>).  This case could be in P, or not in P but not NP-hard.</p>

<hr>

<p><em>Proof of Lemma 1.</em> One can faithfully re-encode any problem instance given in the form above into a representation that uses only <span class="math-container">$O(\log n)$</span> bits, as follows. For each of the <span class="math-container">$2^d$</span> possible vectors in <span class="math-container">$\{0,1\}^d$</span>, write down the number of times that vector occurs in <span class="math-container">$V$</span>.  Write down <span class="math-container">$\ell$</span> and each entry of <span class="math-container">$\mathbf b$</span>.  </p>

<p>There are <span class="math-container">$2^d + d + 1$</span> numbers written, and each number is at most <span class="math-container">$n$</span>, so the encoding size is <span class="math-container">$\Theta(2^d\log n)$</span> bits.)  It follows that (for fixed <span class="math-container">$d$</span>) the number of distinct instances of size <span class="math-container">$n$</span> is polynomial in <span class="math-container">$n$</span>.  This implies (details next) that the decision problem cannot be NP-hard unless P=NP.</p>

<p>In more detail, let <span class="math-container">$L$</span> denote the language for the problem encoded as first defined.  Assume that <span class="math-container">$L$</span> is NP-hard.  Define <span class="math-container">$L' = \{(f(V, \mathbf b, \ell), 1^{|V|}) : (V, \mathbf b, \ell) \in L\}$</span>, where <span class="math-container">$f(V, \mathbf b, \ell)$</span> is the re-encoding of the instance as described above (into <span class="math-container">$O(\log |V|)$</span> bits), and <span class="math-container">$1^{|V|}$</span> is <span class="math-container">$|V|$</span> in unary.  </p>

<p><span class="math-container">$L$</span> reduces in poly-time to <span class="math-container">$L'$</span>, so <span class="math-container">$L'$</span> is also NP-hard.  But <span class="math-container">$L'$</span> is sparse (the number of elements of size <span class="math-container">$n$</span> is polynomial in <span class="math-container">$n$</span>), so P=NP (by <a href="https://en.wikipedia.org/wiki/Mahaney%27s_theorem" rel="nofollow noreferrer">Mahaney's theorem</a>). <span class="math-container">$~~~\Box$</span></p>

<hr>

<p><em>Proof of Lemma 2.</em> 
The algorithm will solve the following more general problem.
The input is <span class="math-container">$(V, \mathbf B)$</span> where <span class="math-container">$V=\{x_1,\ldots,x_n\}$</span> (as before) and <span class="math-container">$\mathbf B = (B_1, B_2, \ldots, B_\ell)$</span> is a collection of <span class="math-container">$\ell$</span> vectors, 
where each <span class="math-container">$B_j$</span> is in <span class="math-container">$\{0,1,\ldots,n\}^d$</span>.
The problem is to decide whether there is a partition of <span class="math-container">$V$</span> into parts
<span class="math-container">$(V_1, V_2, \ldots, V_\ell)$</span> such that <span class="math-container">$\forall j,~\sum_{x_i\in V_j} x_i = B_j$</span>.</p>

<p>This differs from the original problem in two ways.  First, each part <span class="math-container">$V_j$</span> in the partition can have a different required sum <span class="math-container">$B_j$</span> (instead of <span class="math-container">$\mathbf b$</span>).  Second, equality must hold (the sum must equal <span class="math-container">$B_j$</span>, rather being <span class="math-container">$\le \mathbf b$</span>).  </p>

<p>A given instance <span class="math-container">$(V, \mathbf b, \ell)$</span> of the original problem poly-time reduces to this one by considering all instances of this one of the form <span class="math-container">$(V, \mathbf B)$</span> where each <span class="math-container">$B_i$</span> is in <span class="math-container">$\{0,1,\ldots,n\}^d$</span> and <span class="math-container">$B_i \le b$</span>.  There are <span class="math-container">$O(n^{d\ell})$</span> such instances, which is polynomial since <span class="math-container">$d$</span> and <span class="math-container">$\ell$</span> are constant.  The original instance will have a solution if and only if at least one of the latter instances does.</p>

<p>The algorithm solves the variant using the following dynamic program.  Fix an instance <span class="math-container">$(V,\mathbf B)$</span> of the problem.  Let <span class="math-container">$V=\{x_1,\ldots,x_n\}$</span> and <span class="math-container">$\mathbf B = (B_1,\ldots,B_\ell)$</span>. So <span class="math-container">$x_i\in\{0,1\}^d$</span> and <span class="math-container">$B_j\in \{0,1,\ldots,n\}^d$</span> for each <span class="math-container">$i$</span> and <span class="math-container">$j$</span>.</p>

<p>Define the <em>signature</em> of the instance <span class="math-container">$(V, \mathbf B)$</span> (following the proof of Lemma 1) to be obtained by replacing <span class="math-container">$V$</span> by the natural encoding of the function <span class="math-container">$f_V$</span> such that, for each <span class="math-container">$x\in\{0,1\}^d$</span>, <span class="math-container">$f_V(x)$</span> is the number of times <span class="math-container">$x$</span> occurs in <span class="math-container">$V$</span>.  Note that any two instances with the same signature are equivalent, in that they have the same answer.</p>

<p>The signature is determined by <span class="math-container">$2^d + d\ell$</span> numbers, each in <span class="math-container">$\{0,1,\ldots,n\}$</span>, so the number of possible signatures (among instances with the given parameters <span class="math-container">$d,\ell, n$</span>) is <span class="math-container">$O(n^{2^d+d\ell})$</span>, which (given that <span class="math-container">$d$</span> and <span class="math-container">$\ell$</span> are constant) is polynomial in <span class="math-container">$n$</span>.  Furthermore, the number of possible signatures of all "smaller" instances (meaning those where <span class="math-container">$n$</span> is smaller than the given <span class="math-container">$n$</span>) is at most a factor of <span class="math-container">$n$</span> larger, so also polynomial in <span class="math-container">$n$</span>.</p>

<p>Now we can proceed via dynamic programming.  Fix the given instance <span class="math-container">$(V, \mathbf B)$</span>. For the base case, if <span class="math-container">$V=\emptyset$</span> (that is, <span class="math-container">$n=0$</span>), then the instance is feasible iff each <span class="math-container">$\mathbf B \equiv \mathbf 0$</span>.  Otherwise <span class="math-container">$x_n$</span> can go into one of the parts <span class="math-container">$V_j$</span> for <span class="math-container">$j\in\{1,2,\ldots,\ell\}$</span>, such that removing <span class="math-container">$x_n$</span> from that part gives a solution to the problem obtained by subtracting <span class="math-container">$x_n$</span> from <span class="math-container">$\mathbf B_j$</span> (as long as <span class="math-container">$x_n\le \mathbf B_j$</span>; if not <span class="math-container">$x_n$</span> cannot go in <span class="math-container">$V_j$</span>).  </p>

<p>For each of the (at most) <span class="math-container">$\ell$</span> possible ways of placing <span class="math-container">$x_n$</span>, recursively determine whether the resulting subproblem has a solution.  The original problem will have a solution if and only if one of these subproblems does.</p>

<p>Furthermore, memoize -- keep a cache of the answers to already-solved subproblems, indexed by signature.  When encountering a given subproblem, check whether any subproblem with the same signature has already been answered, and if so use that answer instead of recursing.  Because there are only polynomially many distinct signatures of smaller subproblems, the dynamic-programming algorithm will solve only polynomially many subproblems, so will run in time polynomial in <span class="math-container">$n$</span>. <span class="math-container">$~~\Box$</span>.</p>

<p><em>EDIT: As pointed out in the comments, an easier approach is (similarly to the proof of Lemma 3 below) to formulate an ILP of constant dimension, with a variable <span class="math-container">$y_{xj}$</span> for each <span class="math-container">$x\in\{0,1\}^d$</span> and <span class="math-container">$j\in\{1,\ldots,\ell\}$</span> representing the number of vectors in <span class="math-container">$V$</span> that are equal to <span class="math-container">$x$</span> and are assigned to part <span class="math-container">$V_j$</span>.</em></p>

<p>The proof above raises the question of whether the variant defined in the proof is NP-hard when <span class="math-container">$\ell$</span> is not constant.  (It might be, even if the original problem is not.)</p>

<hr>

<p><em>Proof of Lemma 3.</em>
The proof is an elaboration of @Gamow's answer in the comments.</p>

<p>Use the following equivalent problem formulation: <em>Given a collection <span class="math-container">$V=(S_1, S_2, \ldots, S_n)$</span> of subsets of <span class="math-container">$\{1,2,\ldots, d\}$</span>, where <span class="math-container">$d$</span> is constant, partition <span class="math-container">$V$</span> into a minimum number of parts, such that within each part each element <span class="math-container">$j$</span> occurs in more than <span class="math-container">$b_j$</span> subsets.</em>  Here is the algorithm.</p>

<p>Fix an input <span class="math-container">$V=(S_1, \ldots, S_n)$</span> of subsets of <span class="math-container">$\{1,2,\ldots, d\}$</span>.
Let <span class="math-container">$\mathcal S_d$</span> denote the set of non-empty subsets of <span class="math-container">$\{1,2,\ldots,d\}$</span>.
Let <span class="math-container">$\mathcal P_d$</span> denote the set of <em>possible parts</em>, that is, multi-subsets of <span class="math-container">$\mathcal S_d$</span> in which each element <span class="math-container">$j$</span> occurs at most <span class="math-container">$b_j$</span> times.
The goal is to partition the input <span class="math-container">$V$</span> into a minimum number of parts, each of which is in <span class="math-container">$\mathcal P_d$</span>.</p>

<p>Note that <span class="math-container">$|\mathcal S_d| &lt; 2^d$</span> and <span class="math-container">$|\mathcal P_d| \ll (bd)^{bd}$</span>, so (as <span class="math-container">$b$</span> and <span class="math-container">$d$</span> are constant) there are constantly many possible subsets, and constantly many possible parts.</p>

<p>For each subset <span class="math-container">$S\in\mathcal S_d$</span> and possible part <span class="math-container">$p\in\mathcal P_d$</span>, let <span class="math-container">$n(S, p)$</span> (either 0 or 1) denote the number of times that <span class="math-container">$S$</span> occurs in <span class="math-container">$p$</span>.</p>

<p>For each possible subset <span class="math-container">$S\in\mathcal S_d$</span>, count the number of times that <span class="math-container">$S$</span> occurs in the input <span class="math-container">$V$</span>. Let <span class="math-container">$n(S, V)$</span> denote this number. </p>

<p>Finally, construct and solve the following integer linear program (ILP), with an integer-valued variable <span class="math-container">$x_p$</span> for each possible part <span class="math-container">$p\in\mathcal P_d$</span>:</p>

<p><span class="math-container">$$\text{minimize} \sum_{p\in\mathcal P_d} x_p \text{ subject to }$$</span></p>

<p><span class="math-container">$$\begin{align}
(\forall S\in \mathcal S_d) &amp;&amp; \sum_{p\in\mathcal P_d} n(S, p)\,x_p &amp;{} = n(S, V) \\
(\forall p\in \mathcal P_d) &amp;&amp; x_p &amp;{} \in \{0,1,2,\ldots\} \\
\end{align}$$</span></p>

<p>For <span class="math-container">$\max_j b_j = O(1)$</span> and <span class="math-container">$d=O(1)$</span>, the ILP has constant dimension (and a constant number of constraints) so can be solved in constant time in the real RAM model (by <a href="https://doi.org/10.1145/2422.322418" rel="nofollow noreferrer">Megiddo's algorithm</a> or <a href="https://doi.org/10.1145/3155312" rel="nofollow noreferrer">subsequent improvements</a>).  The optimal value is the answer for the given instance <span class="math-container">$V$</span>. <span class="math-container">$~~\Box$</span></p>

<p>The real RAM model does not account for bit complexity of arithmetic operations.  But in each feasible solution to this ILP each coordinate has <span class="math-container">$O(\log n)$</span> bits, so presumably the ILP can be solved in polylog<span class="math-container">$(n)$</span> time in the standard RAM model,
so this approach should also yield a linear-time algorithm in the standard RAM model.</p>

CC BY-SA 4.0
2020-05-20T08:12:31.723Z
Since I just wanted to know if it was NP-Hard or not, this pretty much solves it. As for Lemma 2, here is an easier way of proving it via an ILP. Since every item is from $\{0,1\}^d$, there are only $2^d$ "types" of items. Then we can represent the items as $(a_1,a_2,\ldots,a_{2^d})$, where $a_i$ is the number of items of the $i$th type. Then we make an ILP with variables $x_{ij}$, which represent the number of items of type $i$ assigned to bin $j$. The constraints naturally follow. Since $d=O(1),l=O(1)$, this ILP has constant size and we can thus check its feasibility in poly time.
gov
CC BY-SA 4.0
2020-05-20T01:23:08.477Z
2020-05-20T13:22:14.837Z
2020-05-20T13:22:14.837Z
Neal Young
<p>The paper <a href="https://cs.brown.edu/people/seny/pubs/vbponline.pdf" rel="nofollow noreferrer">https://cs.brown.edu/people/seny/pubs/vbponline.pdf</a> discusses <span class="math-container">$\{0,1\}$</span>-Vector Bin packing in the online setting and give lower bounds. However, they do not mention anything about the complexity of the problem in the offline setting. I could not find any other papers mentioning this either. </p>

<p>Formally, the problem is as follows: Given a set of vectors <span class="math-container">$V=\{x_1,x_2,\ldots,x_n\}$</span>, where each <span class="math-container">$x_i\in\{0,1\}^d$</span>, and a vector <span class="math-container">$\textbf{b}=(b_1,b_2,\ldots,b_d)\in \mathbb{Z}_+^d$</span>, partition <span class="math-container">$V$</span> into <span class="math-container">$V_1,V_2,\ldots,V_l$</span> such that <span class="math-container">$\forall~j,\sum_{x_i\in V_j} x_i \leq \textbf{b}$</span>. Then the objective is to minimize the number of partitions, <span class="math-container">$l$</span>.</p>

<p>While the problem in general can easily be seen to be NP-Hard from Independent set or, as Yonatan pointed out, <span class="math-container">$k$</span>-colouring, I'm interested in the case when the vectors are from <span class="math-container">$\{0,1\}^d$</span>, where <span class="math-container">$d=O(1)$</span>. It is known that <span class="math-container">$[0,1]$</span>-vector packing is NP-Hard even under this restriction, because it is a generalization of bin packing. However, I did not find anything for the <span class="math-container">$\{0,1\}$</span> case. Is this problem NP-Hard?</p>

<p>Neal Young has given an excellent answer for the case when the vector <span class="math-container">$\textbf{b}$</span> has <span class="math-container">$\forall ~i,b_i=O(1)$</span>. This leaves the case where <span class="math-container">$b_i$</span> is not constant. In particular, <span class="math-container">$b_i=\Omega(n)$</span> seems to remain hard. </p>

<p>Edit: It seems that the problem has been considered, at least in the knapsack context, <a href="https://www.imacm.uni-wuppertal.de/fileadmin/imacm/preprints/amna_opap_09_02.pdf" rel="nofollow noreferrer">here</a>. Their algorithm for the <span class="math-container">$d=2$</span> case seems very non-trivial. This seems to suggest that the ILP approach suggested by Gamow wouldn't work. </p>

CC BY-SA 4.0
2020-05-03T20:47:24.010Z
One can show hardness by reduction from $k$-coloring. Let $G=(V,E)$ be an instance thereof. For each vertex $v \in V$, let $u_v$ be a flattened version of the adjacency matrix of $G(V, E_v)$, where $E_v$ is the set of edges containing $v$ as an endpoint. When trying to pack these vectors, we run into trouble exactly when we try to pack the flattened matrices corresponding to two neighboring vertices into the same bin, i.e. when the two vertices should not be given the same color. Thus, finding a packing of $\{u_v\}$ into $k$ bins is equivalent to finding a $k$-coloring of $G$.
Yonatan N
CC BY-SA 4.0
2020-05-04T04:19:02.873Z
Thanks, but I was interested in the case where the vectors have constant dimension. I've edited the question to mention this.
gov
CC BY-SA 4.0
2020-05-04T08:09:32.567Z
That's one of these annoying cases: after reveiving a perfectly good answer, the question is edited and changed to something completely different. The new (second) version of the problem is solvable in polynomial time, since it can be formulated as an ILP with constant dimension.
Gamow
CC BY-SA 4.0
2020-05-04T19:07:21.597Z
I apologize for the mistake from my side.

Thank you for the suggestion. As for your answer, I still have some trouble understanding how to formulate the ILP so that it has constant dimension. If the question is to decide whether the items can fit into $K$ bins, won't the ILP have some $2^dK $ variables? If you could clarify this and add this as an answer, I could accept it. Again, sorry for the initial mistake.
gov
CC BY-SA 4.0
2020-05-06T17:48:02.690Z
If the restriction is that the vectors assigned to one bin must sum up to less than **1**, the all ones vector, then I believe you can solve it using a simple ILP. I could not come up with such an ILP for the case when the bin sizes are not necessarily **1**.
gov
<reference-request><np-hardness><packing>
Is $\{0,1\}$-Vector bin packing NP-Hard when vectors have constant dimension?
gov
# Is $\{0,1\}$-Vector bin packing NP-Hard when vectors have constant dimension?

(Asked by: username_0 on 2020-05-03)

The paper <https://cs.brown.edu/people/seny/pubs/vbponline.pdf> discusses $\{0,1\}$-Vector Bin packing in the online setting and give lower bounds. However, they do not mention anything about the complexity of the problem in the offline setting. I could not find any other papers mentioning this either.

Formally, the problem is as follows: Given a set of vectors $V=\{x\_1,x\_2,\ldots,x\_n\}$, where each $x\_i\in\{0,1\}^d$, and a vector $\textbf{b}=(b\_1,b\_2,\ldots,b\_d)\in \mathbb{Z}\_+^d$, partition $V$ into $V\_1,V\_2,\ldots,V\_l$ such that $\forall~j,\sum\_{x\_i\in V\_j} x\_i \leq \textbf{b}$. Then the objective is to minimize the number of partitions, $l$.

While the problem in general can easily be seen to be NP-Hard from Independent set or, as Yonatan pointed out, $k$-colouring, I'm interested in the case when the vectors are from $\{0,1\}^d$, where $d=O(1)$. It is known that $[0,1]$-vector packing is NP-Hard even under this restriction, because it is a generalization of bin packing. However, I did not find anything for the $\{0,1\}$ case. Is this problem NP-Hard?

username_3 has given an excellent answer for the case when the vector $\textbf{b}$ has $\forall ~i,b\_i=O(1)$. This leaves the case where $b\_i$ is not constant. In particular, $b\_i=\Omega(n)$ seems to remain hard.

Edit: It seems that the problem has been considered, at least in the knapsack context, [here](https://www.imacm.uni-wuppertal.de/fileadmin/imacm/preprints/amna_opap_09_02.pdf). Their algorithm for the $d=2$ case seems very non-trivial. This seems to suggest that the ILP approach suggested by username_2 wouldn't work.

**Tags:** reference-request, np-hardness, packing

> **Comments:**
> **username_1**: One can show hardness by reduction from $k$-coloring. Let $G=(V,E)$ be an instance thereof. For each vertex $v \in V$, let $u_v$ be a flattened version of the adjacency matrix of $G(V, E_v)$, where $E_v$ is the set of edges containing $v$ as an endpoint. When trying to pack these vectors, we run into trouble exactly when we try to pack the flattened matrices corresponding to two neighboring vertices into the same bin, i.e. when the two vertices should not be given the same color. Thus, finding a packing of $\{u_v\}$ into $k$ bins is equivalent to finding a $k$-coloring of $G$.  
> **username_0**: Thanks, but I was interested in the case where the vectors have constant dimension. I've edited the question to mention this.  
> **username_2**: That's one of these annoying cases: after reveiving a perfectly good answer, the question is edited and changed to something completely different. The new (second) version of the problem is solvable in polynomial time, since it can be formulated as an ILP with constant dimension.  
> **username_0**: I apologize for the mistake from my side.  Thank you for the suggestion. As for your answer, I still have some trouble understanding how to formulate the ILP so that it has constant dimension. If the question is to decide whether the items can fit into $K$ bins, won't the ILP have some $2^dK $ variables? If you could clarify this and add this as an answer, I could accept it. Again, sorry for the initial mistake.  
> **username_0**: If the restriction is that the vectors assigned to one bin must sum up to less than **1**, the all ones vector, then I believe you can solve it using a simple ILP. I could not come up with such an ILP for the case when the bin sizes are not necessarily **1**.  

---

## 1 answers

### Answer by username_3 on 2020-05-20. Score: 4 | Accepted answer

*EDIT: Merged the two answers.*

Here's the problem statement:

*The input is $(V, \mathbf b, \ell)$, where $V=\{x\_1,x\_2,\ldots,x\_n\}$ with each $x\_i\in\{0,1\}^d$ (where $d$ is constant), vector $\textbf{b}=(b\_1,b\_2,\ldots,b\_d)\in \mathbb{Z}\_+^d$, and $\ell$ is an integer.
The problem is to decide whether $V$ can be partitioned into $\ell$ parts $V\_1,V\_2,\ldots,V\_\ell$ such that $\forall~j,\sum\_{x\_i\in V\_j} x\_i \leq \textbf{b}$.*

**Lemma 1.** *The problem (with $d=O(1)$) reduces to a sparse language, so is not NP-hard unless P=NP.*

**Lemma 2.** *For $d=O(1)$ and $\ell=O(1)$, the problem can be solved in polynomial time via dynamic programming (EDIT: or an ILP of constant dimension).*

**Lemma 3.** *For $d=O(1)$ and $\max\_j b\_j=O(1)$, the problem can be solved in linear time (in the real RAM model) via an ILP of constant dimension.*

This leaves open the complexity of the case when $\ell$ and $\max\_j b\_j$ are both allowed to grow (while $d=O(1)$). This case could be in P, or not in P but not NP-hard.

---

*Proof of Lemma 1.* One can faithfully re-encode any problem instance given in the form above into a representation that uses only $O(\log n)$ bits, as follows. For each of the $2^d$ possible vectors in $\{0,1\}^d$, write down the number of times that vector occurs in $V$. Write down $\ell$ and each entry of $\mathbf b$.

There are $2^d + d + 1$ numbers written, and each number is at most $n$, so the encoding size is $\Theta(2^d\log n)$ bits.) It follows that (for fixed $d$) the number of distinct instances of size $n$ is polynomial in $n$. This implies (details next) that the decision problem cannot be NP-hard unless P=NP.

In more detail, let $L$ denote the language for the problem encoded as first defined. Assume that $L$ is NP-hard. Define $L' = \{(f(V, \mathbf b, \ell), 1^{|V|}) : (V, \mathbf b, \ell) \in L\}$, where $f(V, \mathbf b, \ell)$ is the re-encoding of the instance as described above (into $O(\log |V|)$ bits), and $1^{|V|}$ is $|V|$ in unary.

$L$ reduces in poly-time to $L'$, so $L'$ is also NP-hard. But $L'$ is sparse (the number of elements of size $n$ is polynomial in $n$), so P=NP (by [Mahaney's theorem](https://en.wikipedia.org/wiki/Mahaney%27s_theorem)). $~~~\Box$

---

*Proof of Lemma 2.*
The algorithm will solve the following more general problem.
The input is $(V, \mathbf B)$ where $V=\{x\_1,\ldots,x\_n\}$ (as before) and $\mathbf B = (B\_1, B\_2, \ldots, B\_\ell)$ is a collection of $\ell$ vectors,
where each $B\_j$ is in $\{0,1,\ldots,n\}^d$.
The problem is to decide whether there is a partition of $V$ into parts
$(V\_1, V\_2, \ldots, V\_\ell)$ such that $\forall j,~\sum\_{x\_i\in V\_j} x\_i = B\_j$.

This differs from the original problem in two ways. First, each part $V\_j$ in the partition can have a different required sum $B\_j$ (instead of $\mathbf b$). Second, equality must hold (the sum must equal $B\_j$, rather being $\le \mathbf b$).

A given instance $(V, \mathbf b, \ell)$ of the original problem poly-time reduces to this one by considering all instances of this one of the form $(V, \mathbf B)$ where each $B\_i$ is in $\{0,1,\ldots,n\}^d$ and $B\_i \le b$. There are $O(n^{d\ell})$ such instances, which is polynomial since $d$ and $\ell$ are constant. The original instance will have a solution if and only if at least one of the latter instances does.

The algorithm solves the variant using the following dynamic program. Fix an instance $(V,\mathbf B)$ of the problem. Let $V=\{x\_1,\ldots,x\_n\}$ and $\mathbf B = (B\_1,\ldots,B\_\ell)$. So $x\_i\in\{0,1\}^d$ and $B\_j\in \{0,1,\ldots,n\}^d$ for each $i$ and $j$.

Define the *signature* of the instance $(V, \mathbf B)$ (following the proof of Lemma 1) to be obtained by replacing $V$ by the natural encoding of the function $f\_V$ such that, for each $x\in\{0,1\}^d$, $f\_V(x)$ is the number of times $x$ occurs in $V$. Note that any two instances with the same signature are equivalent, in that they have the same answer.

The signature is determined by $2^d + d\ell$ numbers, each in $\{0,1,\ldots,n\}$, so the number of possible signatures (among instances with the given parameters $d,\ell, n$) is $O(n^{2^d+d\ell})$, which (given that $d$ and $\ell$ are constant) is polynomial in $n$. Furthermore, the number of possible signatures of all "smaller" instances (meaning those where $n$ is smaller than the given $n$) is at most a factor of $n$ larger, so also polynomial in $n$.

Now we can proceed via dynamic programming. Fix the given instance $(V, \mathbf B)$. For the base case, if $V=\emptyset$ (that is, $n=0$), then the instance is feasible iff each $\mathbf B \equiv \mathbf 0$. Otherwise $x\_n$ can go into one of the parts $V\_j$ for $j\in\{1,2,\ldots,\ell\}$, such that removing $x\_n$ from that part gives a solution to the problem obtained by subtracting $x\_n$ from $\mathbf B\_j$ (as long as $x\_n\le \mathbf B\_j$; if not $x\_n$ cannot go in $V\_j$).

For each of the (at most) $\ell$ possible ways of placing $x\_n$, recursively determine whether the resulting subproblem has a solution. The original problem will have a solution if and only if one of these subproblems does.

Furthermore, memoize -- keep a cache of the answers to already-solved subproblems, indexed by signature. When encountering a given subproblem, check whether any subproblem with the same signature has already been answered, and if so use that answer instead of recursing. Because there are only polynomially many distinct signatures of smaller subproblems, the dynamic-programming algorithm will solve only polynomially many subproblems, so will run in time polynomial in $n$. $~~\Box$.

*EDIT: As pointed out in the comments, an easier approach is (similarly to the proof of Lemma 3 below) to formulate an ILP of constant dimension, with a variable $y\_{xj}$ for each $x\in\{0,1\}^d$ and $j\in\{1,\ldots,\ell\}$ representing the number of vectors in $V$ that are equal to $x$ and are assigned to part $V\_j$.*

The proof above raises the question of whether the variant defined in the proof is NP-hard when $\ell$ is not constant. (It might be, even if the original problem is not.)

---

*Proof of Lemma 3.*
The proof is an elaboration of @username_2's answer in the comments.

Use the following equivalent problem formulation: *Given a collection $V=(S\_1, S\_2, \ldots, S\_n)$ of subsets of $\{1,2,\ldots, d\}$, where $d$ is constant, partition $V$ into a minimum number of parts, such that within each part each element $j$ occurs in more than $b\_j$ subsets.* Here is the algorithm.

Fix an input $V=(S\_1, \ldots, S\_n)$ of subsets of $\{1,2,\ldots, d\}$.
Let $\mathcal S\_d$ denote the set of non-empty subsets of $\{1,2,\ldots,d\}$.
Let $\mathcal P\_d$ denote the set of *possible parts*, that is, multi-subsets of $\mathcal S\_d$ in which each element $j$ occurs at most $b\_j$ times.
The goal is to partition the input $V$ into a minimum number of parts, each of which is in $\mathcal P\_d$.

Note that $|\mathcal S\_d| < 2^d$ and $|\mathcal P\_d| \ll (bd)^{bd}$, so (as $b$ and $d$ are constant) there are constantly many possible subsets, and constantly many possible parts.

For each subset $S\in\mathcal S\_d$ and possible part $p\in\mathcal P\_d$, let $n(S, p)$ (either 0 or 1) denote the number of times that $S$ occurs in $p$.

For each possible subset $S\in\mathcal S\_d$, count the number of times that $S$ occurs in the input $V$. Let $n(S, V)$ denote this number.

Finally, construct and solve the following integer linear program (ILP), with an integer-valued variable $x\_p$ for each possible part $p\in\mathcal P\_d$:

$$\text{minimize} \sum\_{p\in\mathcal P\_d} x\_p \text{ subject to }$$

$$\begin{align}
(\forall S\in \mathcal S\_d) && \sum\_{p\in\mathcal P\_d} n(S, p)\,x\_p &{} = n(S, V) \\
(\forall p\in \mathcal P\_d) && x\_p &{} \in \{0,1,2,\ldots\} \\
\end{align}$$

For $\max\_j b\_j = O(1)$ and $d=O(1)$, the ILP has constant dimension (and a constant number of constraints) so can be solved in constant time in the real RAM model (by [Megiddo's algorithm](https://doi.org/10.1145/2422.322418) or [subsequent improvements](https://doi.org/10.1145/3155312)). The optimal value is the answer for the given instance $V$. $~~\Box$

The real RAM model does not account for bit complexity of arithmetic operations. But in each feasible solution to this ILP each coordinate has $O(\log n)$ bits, so presumably the ILP can be solved in polylog$(n)$ time in the standard RAM model,
so this approach should also yield a linear-time algorithm in the standard RAM model.

> **Comments:**
> **username_0**: Since I just wanted to know if it was NP-Hard or not, this pretty much solves it. As for Lemma 2, here is an easier way of proving it via an ILP. Since every item is from $\{0,1\}^d$, there are only $2^d$ "types" of items. Then we can represent the items as $(a_1,a_2,\ldots,a_{2^d})$, where $a_i$ is the number of items of the $i$th type. Then we make an ILP with variables $x_{ij}$, which represent the number of items of type $i$ assigned to bin $j$. The constraints naturally follow. Since $d=O(1),l=O(1)$, this ILP has constant size and we can thus check its feasibility in poly time.  

---

