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?

The problem is NP hard. Here's a reduction to it from 4colorability. 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 edgesquavectors. [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 codimension2 subspace missing $S$ if and only if $G$ is 4colorable. Since 4colorability is known to be an NPcomplete problem, the vector subspace problem is also NPhard. 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. 

