<p>I'm quite interested in the following algorithmic problem, on which I can't find any information. Phrased as a decision problem:</p>
<blockquote>
<p>Given a set of vectors <span class="math-container">$V$</span> in <span class="math-container">$\text{GF}(2)^n$</span>, a vector <span class="math-container">$\mathbf u$</span> in <span class="math-container">$\text{GF}(2)^n$</span>, and an integer <span class="math-container">$k$</span>, decide whether there exists a subset <span class="math-container">$S \subseteq V$</span> such that <span class="math-container">$|S|\leq k$</span> and  <span class="math-container">$\sum_{\mathbf v\in S} \mathbf v = \mathbf u$</span>.</p>
</blockquote>
<p>Note that despite sounding similar to the subset sum problem, it's actually quite different – in particular without the <span class="math-container">$|S|\leq k$</span> restriction it's basic linear algebra. My attempts to google the problem have failed so far. Is this a problem already explored in some papers? Is it equivalent to another well-known problem? Is it solvable by a practical algorithm? Is it NP-complete? I would be surprised if there was no literature about this problem at all given the short formulation.</p>
<p>What I figured out by myself is that this problem could be polynomially reduced to the problem of</p>
<blockquote>
<p>Given a set of vectors <span class="math-container">$V$</span> in <span class="math-container">$\text{GF}(2)^n$</span>, a vector <span class="math-container">$\mathbf u$</span> in <span class="math-container">$\text{GF}(2)^n$</span>, and an integer <span class="math-container">$k$</span>, decide whether there exists a subset <span class="math-container">$S \subseteq V$</span> such that the vector <span class="math-container">$\mathbf u+\sum_{\mathbf v\in S} \mathbf v$</span> consists of at most <span class="math-container">$k$</span> ones.</p>
</blockquote>
<p>Maybe this one is better-known?</p>

CC BY-SA 4.0
2021-02-19T07:27:24.717Z
This is answered in https://cstheory.stackexchange.com/a/10402/. See also https://cstheory.stackexchange.com/q/27460/.
Emil Jeřábek
CC BY-SA 4.0
2021-02-19T17:55:31.060Z
Thank you! I've proved it's NP-complete by myself in the meantime, but having papers to refer to is going to be really useful for me.
Maja Trela
<time-complexity><linear-algebra><finite-fields>
Looking for information about a problem of a least subset of vectors modulo 2 summing to another vector
Maja Trela
# Looking for information about a problem of a least subset of vectors modulo 2 summing to another vector

(Asked by: username_0 on 2021-02-19)

I'm quite interested in the following algorithmic problem, on which I can't find any information. Phrased as a decision problem:

> Given a set of vectors $V$ in $\text{GF}(2)^n$, a vector $\mathbf u$ in $\text{GF}(2)^n$, and an integer $k$, decide whether there exists a subset $S \subseteq V$ such that $|S|\leq k$ and $\sum\_{\mathbf v\in S} \mathbf v = \mathbf u$.

Note that despite sounding similar to the subset sum problem, it's actually quite different – in particular without the $|S|\leq k$ restriction it's basic linear algebra. My attempts to google the problem have failed so far. Is this a problem already explored in some papers? Is it equivalent to another well-known problem? Is it solvable by a practical algorithm? Is it NP-complete? I would be surprised if there was no literature about this problem at all given the short formulation.

What I figured out by myself is that this problem could be polynomially reduced to the problem of

> Given a set of vectors $V$ in $\text{GF}(2)^n$, a vector $\mathbf u$ in $\text{GF}(2)^n$, and an integer $k$, decide whether there exists a subset $S \subseteq V$ such that the vector $\mathbf u+\sum\_{\mathbf v\in S} \mathbf v$ consists of at most $k$ ones.

Maybe this one is better-known?

**Tags:** time-complexity, linear-algebra, finite-fields

> **Comments:**
> **username_1**: This is answered in https://cstheory.stackexchange.com/a/10402/. See also https://cstheory.stackexchange.com/q/27460/.  
> **username_0**: Thank you! I've proved it's NP-complete by myself in the meantime, but having papers to refer to is going to be really useful for me.  

---

## 0 answers

