Finding a subspace disjoint from a union of subspaces

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.

• I wonder if one can encode 3SAT (satisfiability), but that is just a guess. In the special case that the $V_i$ all have dimension 1 (lines) it would be equivalent (in some sense) to find the largest dimension subspace completely covered by lines (the complementary set of one dimensional subspaces). Of course if you mean polynomial in $N$ that would be another matter. Jan 3 '13 at 6:53
• 3Sat is probably a pretty easy way to do this, especially for Z/2, but boy is that unsatisfying. I'd rather have a nice lil algorithm. Jan 3 '13 at 9:33
• My thought was that 3SAT would say NP complete, or do you want an efficient algorithm for small $N$? Jan 3 '13 at 10:20
• The case where $k=\mathbb F_2$ was asked previously, at mathoverflow.net/questions/33035 . My answer there was essentially the last paragraph of Chris Godsil's answer here. Jan 3 '13 at 14:44
• I want small $N$, and I added an edit to this effect. Jan 3 '13 at 18:19

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.
• How sad. Can we do better if $N$ is small. Jan 3 '13 at 18:19
• If $N$ is bounded, inclusion-exclusion might well work. Jan 3 '13 at 18:21