# Efficient algorithm to check if a vector exists in the span of a subset of vectors

I have a binary vector $v \in \mathbb{F}_2^m$ and a set of binary vectors $Q=\{q_1,q_2,\dots,q_n\}$ each belonging to $\mathbb{F}_2^m$ and I know that $v \in \text{span}\{Q\}$ but I want to know if there exists a subset $Q_k \subset Q$ of at most $k$ vectors ( i.e. $|Q_k| \le k < n$ ) such that $v \in \text{span}\{Q_k\}$. Is there a fast algorithm to do this other than the naive way of checking all the subsets of cardinality at most $k$? Assume that all of the operations are done in GF(2).

Given a $m \times n$ matrix $M$ over $\mathbb{F}_2$ and a vector $v \in \mathbb{F}_2^m$, find a vector $x\in \mathbb{F}_2^n$ such that $M x=v$ and the Hamming weight of $x$ is as small as possible.