Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am near the end of a long research problem which was formulated in terms of graph theory to solve a problem in quantum error correcting codes, and I have now constructed some machinery using linear algebra and manifold theory to solve it. I am left with the following problem:

Given a (possibly countably infinite) number of vectors $\vec{v}=[v_{1} \cdot \cdot \cdot v_{n} \cdot \cdot \cdot]$, generated from a finite set of vectors (there exists a basis for the set of vectors), what polynomial time algorithm can I use to check if $\vec{v} \in \{0,1\}^{n}$ for each $\vec{v}$? That is, how can I check through a list of vectors and see if they interesect an n-dimensional hypercube?

Thanks for any suggestions or references.

Edit: The algorithm should be polynomial-time in terms of $n$. We generate the vectors by taking linear combinations of the basis vectors (of the set of vectors) modulo $2$.

share|improve this question
    
I don't understand the question. Can't you check that $v_i \in \{0,1\}$ for all $i = 1,\ldots,n$ in linear time? –  Rahul Oct 19 '12 at 23:57
    
@RahulNarain: Even given an infinite number of vectors to check? –  Samuel Reid Oct 19 '12 at 23:59
1  
Now I really don't understand the question. You want to check a predicate for an infinite number of vectors in polynomial time? Polynomial in what quantity? How is the infinite set of vectors specified? –  Rahul Oct 20 '12 at 0:01
    
@Hurkyl: Yes, they are. –  Samuel Reid Oct 20 '12 at 0:05
1  
In the current revision, aren't all vectors in $\{0,1\}^n$? If not, what do you mean by "modulo 2"? –  Hurkyl Oct 20 '12 at 0:10
show 2 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.