1
$\begingroup$

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$.

  • 0
    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?2012-10-19
  • 0
    @RahulNarain: Even given an infinite number of vectors to check?2012-10-19
  • 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?2012-10-20
  • 0
    @Hurkyl: Yes, they are.2012-10-20
  • 1
    In the current revision, aren't **all** vectors in $\{0,1\}^n$? If not, what do you mean by "modulo 2"?2012-10-20
  • 0
    I think I understand the problem a little better now, but still not entirely. Please let me know if I've followed correctly so far. You have a finite set of basis vectors, say $U = \{\vec u_1, \ldots, \vec u_k\}$. (Are they in $\mathbb R^n$?) You have a possibly countably infinite set of vectors $V = \{\vec v_1, \vec v_2, \ldots\}$ formed by linear combinations from $U$, modulo $2$. (What does "modulo $2$" mean here? Do you mean any $\vec v_j = \alpha_1 \vec u_1 + \cdots + \alpha_k \vec u_k$ with all $\alpha_i \in \{0,1\}$? Is $V$ the set of *all* such $\vec v_j$, or a subset?)...2012-10-20
  • 0
    ...Your problem is then to check whether $V$ is a subset of $\{0,1\}^n$, and to do so in time polynomial in $n$. (What about the dependence on $k$?) Is that right?2012-10-20

0 Answers 0