Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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
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

Your Answer


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

Browse other questions tagged or ask your own question.