1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user777
    Apr 28 at 18:06
  • 1
    $\begingroup$ RP is defined by probabilistic Turing machines. $\endgroup$ Apr 28 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.