Let $k$ be a finite field (I care about $\mathbb F\_p$, especially $\mathbb F\_2$) and let $V\_1,...,V\_N\subset k^n$ be subspaces.  

I want to find a subspace $S\subset k^n$ such that $S\cap V\_i=0$ for each $i$, with $dim(S)$ as large as possible, and I want to do this in polynomial time (in exponential time we can try every possibility, as this is a finite vector space). 


In $\mathbb{R}^n$ this is easy since if we pick $S$ randomly of dimension $n-\max dim(V\_i)$ it will almost always be disjoint from the $V\_i$. Of course, in a finite field you can fill up all of $k^n$ with just 1-dimensional $V\_i$, so this approach fails. 


Thanks


EDIT: What if $N\lt \lt n$, though $dim(V\_i)$ can be around $n/2$ or so. 



Finding a subspace disjoint from a union of subspaces
Let $B$ be the oriented vertex-edge incidence matrix of a graph, viewed as a matrix over $GF(p)$. Let the subspaces $V\_i$ be the 1-dimensional subspaces spanned by the columns of $B$.
There is a subspace of codimension 1 disjoint from these subspaces if and only if there is a non-zero vector $a$ such that no entry of $a^TB$ is zero.


But the columns of $B$ are each of the form $e\_i-e\_j$, for an edge $ij$ of $G$, and we can view $a$ as a function on the vertices of $G$. The condition that no entry of $a^TB$ is zero is then equivalent to the condition that the map from a vertex to the corresponding entry of $a$
is a proper vertex-coloring with $p$ colors. Hence your problem is NP-hard. 


Over GF(2) is can be shown that finding a subspace of codimension two disjoint from the columns is equivalent to 4-coloring.


