2
$\begingroup$

Let suppose that there exists deterministic polynomial algorithm $A$ that approximates the probability that a given boolean circuit $C$ accepts random input with an error at most $\frac{2}{5}$. More precisely, for a boolean circuit $C(x_1, .., x_n)$, $A$ computes a number $A(C)$ such that

$$|\Pr[C(U_n) = 1] - A(C) | \le \frac{2}{5}.$$

$U_n$ is a uniformly distributed random variable with values in $\{0,1\}^n$.

I want to prove that under that assumption $P=BPP$. How can I do that?

Obviously, the problem is with $BPP \subseteq P$. I see that I should create a boolean circuit for "coin tosses", but how?

| cite | improve this question | |
$\endgroup$
1
$\begingroup$

$w$ is an input word, $r$ is a random bits used by a machine to make random decisions.

So, it is obvious that $P \subseteq BPP$, so let's try to show that: $BPP \subseteq P$.

Let $L$ in $BPP$. Then $M(w, r)$ be a machine that decides $L \in BPP$. $M$ is a polynomial probabilistic machine. Let $M'(w, r)$ be an polynomially amplifcated $M$, so: $$w \in L \implies Pr[M'(w, r) \text{ accepts }w] \to 1$$ $$w \not \in L \implies Pr[M'(w, r) \text{ rejects }w] \to 1$$

Now, we construct machine $M_p$ that recognizes $L$ and works in polynomial time.

Let $w$ be a given word to decide. $M_p$ constructs in polynomial time a boolan circuit $C$ equivalent to $M'(w,r)$ where $w$ be hardcoded in that circuit. So, the input word is a random string, $r$.

Note, that our machine $M_p$ So, for a random input $r$ our machine for word $w \in L$ must accept it if $M'$ accepts it with probability $\approx 1$.

But, we must show that $L \in P$ so we cannot use a random word $r$.

Instead, we would like to ask our algorithm about probability of acceptance a random word: $A(C)$. The returned value must be $\approx 0.6$ because possible error is $0.4$. So, if A(C) is $\ge 0.6$ then $M_p$ accepts, else rejects.

It works in polynomial and it accepts the same language:

$$w \in L \implies Pr[M' \text{ accepts w is }] \approx 1 $$ $$w \not \in L \implies Pr[M' \text{ rejects w is }] \approx 1 $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You have the right idea, but some details are shaky. First, $M(x,r)$ is not probabilistic, the idea of talking about a two inputs machine is to consider the coins as part of the input, and talk about the acceptance probability when the second parameter is random, but the machine itself does not toss coins anymore. $M_p$ is not probabilistic, so it is meaningless to talk about its probability to accept $w$. You should always ask yourself probability over what? what is random here? $M_p$ should always output the right answer (which it does). $\endgroup$ – Ariel Aug 26 '17 at 20:33
  • 1
    $\begingroup$ I suggest fixing the success probability after amplification, and write the solution in terms of this probability, rather than some unknown parameter close to $1$. $\endgroup$ – Ariel Aug 26 '17 at 20:37
  • 1
    $\begingroup$ A probabilistic Turing machine is one which tosses coins. $M(x,r)$ is not probabilistic, the fact that you can consider the random variable $M(x,r)$ where $r$ is a uniformly distributed string does not suddenly change the behavior of $M$. The probabilities in your answers are over the input $r$, not the inner coins of $M$. There is indeed a correspondence between a coin tossing machine for $L$, which answers correctly with high probability on any input $x$, and a machine which takes two inputs $x,r$ and for all $x$, agrees with $L$ on most values of $r$, but the distinction is important. $\endgroup$ – Ariel Aug 27 '17 at 21:58

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.