Given: some vector $R=(r_1...r_l)$ - real numbers, and a set of distinct vectors with $+1$ or $-1$ coordinates $$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\ V_2=(c_{2,1} ... c_{2,l}),\\ .....\\ V_n=(c_{n,1} ... c_{n,l})\end{array}$$ each $c_{i,j}$ are $+1$ or $-1$. $n\lt 2^l$ is some number (if $n=2^l$ - problem is trivial.)
Problem: How to find vector $V_i$ which is the most close to $R$ ? ( in the sense of Euclidean distance (suggestions on any other distances are also welcome)).
Of course, we by brute force can check all $V_i$, but is there any way to reduce brute force ? Set of vectors $V_k$ is fixed once and forever, $R$ is coming every millisecond, and algorithm should quickly "decode" $R$ to some $V_i$.
Sub-problems: Is this problem NP-hard ? ( i.e. Is it possible to have algorithm polynomial in the log(n) ? (It is true for some special cases like trivial n=2^l. But what about more general ?))
Given some "hint" vector $V_k$ is possible to answer a question "is it the right answer or not" in some computationally simple way ?
Given some "hint" vector $V_k$ is possible to improve it in some way ?
PS
Does distance function have only global or also local minimums on the set $V_i$ ?
More precisely one should speak about "$\epsilon$-local minimums" for some $\epsilon$.
I.e.
Set of vectors $V_i$ is a metric space (induce metric from $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 given vector $R=(r_1...r_l)$ to $V_i$.
What is the smallest $\epsilon$ for which any $\epsilon$-local minimum is global minimum ?
How it depends on input vector $R=(r_1...r_l)$ ?
