# Definition of RP/poly is not clear!

In Motwani and Raghavan's textbook, p38-39, they states:

A sequence $$C_1, C_2, C_3, \dots$$ of circuits is a circuit family for function $$f_n\colon {0,1}^n \rightarrow \{0,1\}$$ if $$C_n$$ has $$n$$ inputs and computes $$f_n(x_1, x_2, \dots, x_n)$$ at its output for all n-bit inputs $$(x_1, x_2, \dots, x_n)$$. The family $$C$$ is said to be polynomial-sized circuits if the size of $$C_n$$ is bounded above by $$p(n)$$ for every $$n$$, where $$p(\cdot)$$ is polynomial.

It is clear that this is the definition of P/poly. And the next paragraph is the definition of RP/poly.

A randomized circuit family for $$f$$ is a circuit family for $$f$$ that, in addition to the $$n$$ inputs $$x_1, x_2, \dots, x_n$$, takes $$m$$ random bits $$r_1, r_2, \dots, r_m$$, each of which is equiprobably 0 or 1. In addition, for every $$n$$, the circuit $$C_n$$ must satisfy two properties:

1. If $$f_n(x_1, x_2, ..., x_n)=0$$, then the output of the circuit is 0 regardless of the values of random inputs $$r_1, r_2, \dots, r_m$$.
2. If $$f_n(x_1, x_2, ..., x_n)=1$$, the the output of the circuit is 1 with probability at least $$\frac12$$. In other words, at least one half of the $$2^m$$ choices of the bits $$r_1, \dots, r_m$$ will result in the circuit evaluating to 1. We will refer to such $$m$$-tuples $$r_1, r_2, \dots, r_m$$ as witnesses for $$(x_1, x_2, \dots, x_n)$$, in that they testify to the correct value of $$f_n(x_1, x_2, \dots, x_n)$$ when it is 1.

Question: I don't understand what is relationship between $$n$$ and $$m$$ or $$r_1, \dots, r_m$$ and $$f_n(x_1, x_2, \dots, x_n)$$? For example, we have n inputs, i.e. $$x_1, x_2, \dots, x_n$$. But, in second property, they states that at least one half of the $$2^m$$ choices of the bits $$r_1, \dots, r_m$$ will result in the circuit evaluating to 1. Now, how did we bring $$r_1, \dots, r_m$$ to $$f_n(x_1, x_2, \dots, x_n)$$?

The circuit $$C_n$$ has $$n+m$$ inputs, $$x_1,\ldots,x_n,r_1,\ldots,r_m$$. Its size is polynomial in $$n$$, so without loss of generality, $$m$$ is polynomial in $$n$$. What we want is:
1. If $$f_n(x) = 0$$ then $$\Pr_r[C_n(x,r) = 0] = 1$$.
2. If $$f_n(x) = 1$$ then $$\Pr_r[C_n(x,r) = 1] \ge 1/2$$.
Here $$x$$ is shortcut for $$x_1,\ldots,x_n$$, and $$r$$ is shortcut for $$r_1,\ldots,r_m$$.
• Thank you Yuval. Is it correct to say that RP is defined by non-deterministic TM? for example as following: RP/poly defined using non-deterministic TM M such that for $L \subset \{0,1\}^*$ if $x \in L$, then Pr [$M(x, a_{|x|}, r)$accepts ] >= 1/2 and if $x \notin L$, then Pr[$M(x, a_{|x|}, r)$ rejects ] = 1. Is this definition correct? Note that $a_{|x|}$ is an advice and r is the random input. – user777 Apr 28 at 18:06