A few days ago a colleague proposed the following problem.
Let $W$ be a finite subset of a vector space $V$, and let $v\in\langle W\rangle$ (the linear span of $W$). Is there an efficient algorithm to find a subset $S$ of $W$, of minimum size, such that $v\in\langle S\rangle$?
On the one hand, this is "just" linear algebra, so we instinctively expect there to be a good algorithm. On the other hand, it has a combinatorial flavour that seems a bit like a minimum set cover problem, so perhaps it is hard. Of course, this is only interesting in the case that $W$ is linearly dependent since there may be multiple minimal subsets of $W$ that span $v$ with different sizes. (By minimal, I mean that no proper subset will do.) Finding a minimal subset seems easy; finding a minimum subset seems harder, but maybe there is something elementary that we're not noticing.
minimal spanning subset $=$ minimum spanning subset
(All basises of $\langle W\rangle$ has the same number of vectors.)