3 added 918 characters in body

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)$ ?

2 TeXed the question; edited body

# how to find vector (+-1,+-1,+-1,$(\pm1,\pm1,\pm1, ... +-1)\pm1)$ which is most close to given vector (r_1,...r_l) ? Is it NP-problem ? What algorithms are available ?

Given: some vector R=(r_1...r_l) $R=(r_1...r_l)$ - real numbers, and a set of distinct vectors with +1 $+1$ or -1 $-1$ coordinates V1=(c_(1,1) $$\begin{array}{c} V_1=(c_{1,1} ... c_(1,l)) V2=(c_(2,1) c_{1,l}),\\ V_2=(c_{2,1} ... c_(2,l)) c_{2,l}),\\ ..... Vn=(c_(n,1) ....\\ V_n=(c_{n,1} ... c_(n,l)) c_{n,l})\end{array}$$ each c_(i,j) $c_{i,j}$ are +1 $+1$ or -1. "n<2^l" $-1$. $n\lt 2^l$ is some number (if n=2^l $n=2^l$ - problem is trivial.)

Problem: How to find vector Vn $V_i$ which is most close to "R" $R$ ? Of course, we by brute force check all "Vi", $V_i$, but is there any way to reduce brute force ? Set of vectors "Vk" $V_k$ is fixed once and forever, "R" $R$ is coming every

1

# how to find vector (+-1, +-1, +-1, ... +-1) which is most close to given vector (r_1,...r_l) ? Is it NP-problem ? What algorithms are available ?

Given: some vector R=(r_1...r_l) - real numbers, and a set of distinct vectors with +1 or -1 coordinates V1=(c_(1,1) ... c_(1,l)) V2=(c_(2,1) ... c_(2,l)) ..... Vn=(c_(n,1) ... c_(n,l)) each c_(i,j) are +1 or -1. "n<2^l" is some number (if n=2^l - problem is trivial.)

Problem: How to find vector Vn which is most close to "R" ? Of course, we by brute force check all "Vi", but is there any way to reduce brute force ? Set of vectors "Vk" is fixed once and forever, "R" is coming every

## "millisecond", and algorithm should quickly "decode" R to some Vi.

Sub-problems: Is this problem NP-hard ?

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

Given some "hint" vector "Vk" is possible to improve it in some way ?