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.