Largest subspace that doesn't intersect a given set Let V be a vector space over Z/2, and let X be a subset of V.  Is there an algorithm to find the largest possible subspace of V which doesn't intersect X?  Is it NP complete?
 A: The problem is NP hard.  Here's a reduction to it from 4-colorability.  Given a graph with vertex set $G$ [not $V$ because that's supposed to be a vector space] and edge set $E$, form a vector space $V$ over $\mathbb{Z}/2$ having $G$ as a basis.  Identify each edge $e$ with the vector that is the difference of the two endpoints of $e$, and let $S$ be the set of these edges-qua-vectors.  [I know that "difference" is the same as "sum" here, but it helps to think of the edges as differences.]  Then each of the following statements is easily equivalent to the next, for any fixed natural number $t$.  [In the end, I'll only need the case $t=2$.]
(1) $V$ has a subspace of codimension at most $t$ that misses $S$.
(2) There are $t$ linear functionals $f:V\to\mathbb{Z}/2$ such that each edge $e$ is sent to 1 by at least one of these functionals.
(3) There are $t$ linear functionals $f:V\to\mathbb{Z}/2$ such that, for each edge $e$, at least one of these functionals takes different values at the two endpoints of $e$.
(4) There are $t$ functions $g:G\to\mathbb{Z}/2$ such that, for each edge $e$, at least one of these functions takes different values at the two endpoints of $e$.
(5) There is a function $h$ from $G$ to $(\mathbb{Z}/2)^t$ taking different values at the two ends of each edge.
(6) The graph $(G,E)$ is $2^t$-colorable.
In particular, $V$ has a codimension-2 subspace missing $S$ if and only if $G$ is 4-colorable.  Since 4-colorability is known to be an NP-complete problem, the vector subspace problem is also NP-hard.
I believe the "correct" generality for this idea is what's called the critical problem for matroids.  What I've presented is the special case of graphic matroids.
