Skip to main content
Tweeted twitter.com/#!/StackCompSci/status/335665584295534592
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Post Migrated Here from cstheory.stackexchange.com (revisions)
Source Link
MachPortMassenger
MachPortMassenger

Accurate definition of BPP

I'm a bit confused about the definition of BPP. The way BPP is defined in typical text books (Arora/Barak for example) is that if M(x) is a Probabilistic Turing Machine (PTM) that recognizes a language $L(x)$, then $Pr[M(x)=L(x)]> 2/3$. My question is, what is the probability taken over? Arora/Barak remark (7.2) that the probability is taken over internal coin tosses of $M(x)$, i.e., fix a value of $x$, and run all possible $2^{T(|x|)}$ experiments of internal coin tosses, and compute the majority of accept state. But if this is true, then Amplification theorem cannot hold because by definition if the probability is computed by executing all $2^{T(|x|)}$ possible coin-flips, then no matter how many times I run the algorithm, the probability is not going to change. (For example, if I have a bag with 2 red balls and 1 blue ball, then no matter how many times I pick a ball from the bag (and return it), the probability of picking a red ball is going to remain 2/3.)

Basically, a PTM is a random process in two variables: The input string $x \in \{0,1\}^*$ and random coin tosses $ r \in \{0,1\}^{T(|x|)}$. For the amplification theorem to hold, I think one needs to fix a value of $r$ and run the machine on all values of $x$, and compute $Pr[M(x) = L(x)]$. Then for a fixed $x$, running $M(x)$ multiple times will have amplification effect, but if the probability is computed over internal coin tosses, then the Amplification theorem cannot hold.

What am I misunderstanding here?