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