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. So by a counting argument 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 would require an the original problem will also have exponential time circuit complexity (and therefore has no subexponential "algorithm". although your question is more amenable to circuits than algorithms since there's non-uniformity in $l$.algorithm").
|
3 | added 146 characters in body; added 20 characters in body | ||
|
|
||||
|
|
2 | deleted 1 characters in body; edited body | ||
|
If you restrict to the case where |
||||
|
|
1 |
|
||
|
If you restrict to the case where $R \in { \pm1 }^n$ you can encode an arbitrary function $f : {\pm1}^n \rightarrow {\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. So by a counting argument your problem will in general have exponential circuit complexity and therefore would require an exponential time "algorithm". although your question is more amenable to circuits than algorithms since there's non-uniformity in $n$. |
||||
