Let CVal be the language of all $<C,s>$ where $s$ is an $n-$tuple of binary values ($\{0,1\}$), such that $C$ is a variable-free boolean circuit (gates $\wedge$, $\vee$, $\neg$, $0$, $1$), and it outputs $1$ for the entries of $s=(x_1,...,x_n)$.
Given two languages $A,B$, define $A \leq ^{rand} B$ iff there exists a random turing machine $M_f$ with $O(\log n)$ memory, such that for each $x$:
- if $x\notin A$ so $f(x)\notin B$
- else, if $x\in A$, then $P(f(x) \in B) \geq \frac{1}{2}$.
I'd like to show that for each $A\in RP$ exists such a random reduction: $A\leq^{rand} CVal$.
My thoughts were to prove this similarly to how it can be proven that for any $A\in P$ exists a log-space reduction $A\leq_l CVal$ . Meaning, I'd like to show that for every $n$ I can construct $C_n$ such that in probability $\geq \frac{1}{2}$ $\,:\,\,$ $C_n(x)=1$ for every $x$ in length $n$ which is in $A$, and for each $x$ not in $A$ $C_n(x)=0$ for sure, but I'm not sure if perhaps there is an easier way for showing a random reduction $A\leq_{rand} CVal$ for each $A\in RP$?
Thanks!
