Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
I guess Z/2 is $\mathbb F_2=\mathbb Z/2\mathbb Z$, not $\frac12\mathbb Z$. –  Wadim Zudilin Jul 23 '10 at 3:20
    
kevin: let V be the space of pairs of 2 bits. let X be { (1,0), (0,1) }. The space generated by X is all of V, but the space generated by (1,1) does not intersect X. –  Larry D'Anna Jul 23 '10 at 3:25
    
Erm... Are you 100% sure about this statement? I mean, it is very easy to create a subspace $S$ and two points $x,y\notin S$ such that $x+y\in S$. –  fedja Jul 23 '10 at 3:27
    
Yikes. Deleted. –  Kevin Ventullo Jul 23 '10 at 3:41
    
minor nit: you're really asking if it's NP-hard since it's a maximization, not a decision problem –  Suresh Venkat Jul 23 '10 at 4:26

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.