How to find the $\pm 1$ vector that is closest to a given vector $(r_1, \dots, r_l)$? Is it in NP? What algorithms are available? Given a real vector $R = (r_1, \dots, r_l)$ and a set of $n$ distinct vectors
$$\begin{array}{c}
V_1 = (c_{1,1}, \dots, c_{1,l})\\
V_2 = (c_{2,1}, \dots, c_{2,l})\\
\vdots\\\
V_n=(c_{n,1}, \dots, c_{n,l})
\end{array}$$
where $c_{i,j} \in \{\pm 1\}$ and $n \lt 2^l$. Note that if $n = 2^l$ then the problem is trivial.
Problem: How to find the vector $V_i$ whose Euclidean distance to $R$ is minimal? (Suggestions on any other distances are also welcome).
Of course, using brute force we can check all $V_i$, but is there any way to reduce the search space? The set of vectors $V_k$ is fixed once and forever, while vector $R$ is coming every millisecond, and the algorithm should quickly "decode" $R$ to some $V_i$.
Sub-problems: 


*

*Is this problem NP-hard? I.e., is it possible to have an algorithm polynomial in $\log(n)$? It is true for some special cases like the trivial case $n=2^l$, but what about more generally?

*Given some "hint" vector $V_k$, is it possible to answer a question "is it the right answer or not" in some computationally simple way?

*Given some "hint" vector $V_k$, is it possible to improve it in some way?
P.S.
Does the distance function have only global minima? Or does it also have local minima on the set $V_i$? More precisely, one should speak about "$\epsilon$-local minima" for some $\epsilon$. I.e., the set of vectors $V_i$ is a metric space (induce metric from $\mathbb R^n$). Let us say  some function $f$ has  an "$\epsilon$-local minimum" at some point $V_k$
of this set if $f(V_k) < f(V_i)$ for all $V_i \in \epsilon$ - neighborhood  $V_k$).
Consider a distance function from the given vector $R = (r_1, \dots, r_l)$ to $V_i$. What is the smallest $\epsilon$ for which any $\epsilon$-local minimum is a global minimum? How does it depends on input vector $R=(r_1, \dots, r_l)$?
 A: Let the $R_i$ be $\pm 1$ vectors and the $V_i$ be a linear space over GF(2). This then becomes the problem of maximum likelihood decoding of binary linear codes, which is known to be an NP-hard problem. It thus seems likely (although it doesn't follow rigorously) that there's no good way of doing this better than brute force.
A: This problem is NP-hard. It is known (as it has been already mentioned) as the decoding of linear block codes. Here is the reference of the intractability result
E.R. BERLEKAMP, R.J. MCELIECE, and H.C.A. VAN TILBORG, "On the inherent intractability of certain coding problems," IEEE Trans. Inform. Theory, vol. 24, pp. 384– 386, May 1978.
There are some nice relaxations, such as the LP decoder that was introduced in
J. Feldman, M.J. Wainwright and D.R. Karger, "Using linear programming to Decode Binary linear codes," IEEE Transactions on Information Theory, 51:954–972, March 2005.
A: If you restrict to the case where $R \in \{ \pm1 \}^l$ you can encode an arbitrary function $f\colon \{\pm1\}^l\to \pm1$ with appropriate choice of the $V_i$ by augmenting your problem to instead return $1$ if $R = V_i$ for some $i$ and $-1$ otherwise.  If you have an algorithm to solve your original problem then you can solve the augmented problem without adding much by first finding the closest $V_i$ and then checking if $V_i=R$.  Since the augmented problem can encode any function it will in general have exponential circuit complexity, and therefore the original problem will also have exponential circuit complexity (and therefore has no subexponential "algorithm").
A: You may use the concept of semidefinite relaxation (way of arriving at the class of convex semidefinite programs) to solve this problem. This will involve the trick of using the cyclic property of trace operator. Cheers!
