Exercises 11: BPP, ABPP, PP

Proofs to bear in mind

$B P P \subseteq P / p o l y$ main argument:

\forall n, \exists r_{n}, \forall x; | x | = n; M (x, r_{n}) is not wrong

$N P \subseteq P / p o l y ⟹ P H \subseteq P / p o l y$ : see the formulas

Therefore: as $P H \subseteq P / p o l y$ implies that the polynomial hierarchy collapses, it follows that $N P \subseteq B P P$ is unlikely

B P P \subseteq Σ_{2} \cap Π_{2}

$B P P \subseteq Σ_{2}$ :
- $x \in L \in B P P ⟹ \exists t_{0}, \dots, t_{m / n}; \exists r; \underset{i}{⋀} M (x, t_{i} \oplus r)$
- $x \in Σ^{*}$ , Derandomization: $R_{x} = {r ∣ M (x, r) = ⊤}$ If $R_{x}$ is huge, $\exists t_{0}, \dots, t_{m / n}$

EX 1: NP and BPP

1.

If $P = N P$ , then $P H = P$

Indeed, if $P = N P$ , then $c o N P = P = N P$ , and $Σ_{1} = Π_{1} = Π_{0} = Σ_{0}$

Therefore

B P P \subseteq P H \subseteq P

2.

If $N P \subseteq B P P$ , then $A M = M A$

Wrong argument:

$A = B P P, M = N P$ ⟹ if $M \subseteq A$ , then

$M A \subseteq A A \subseteq A$
$A M \subseteq A A \subseteq A$

⟶ wrong argument, because the A in $A$ (a language) is not the same as the one in $M A$ (a protocol)

If $N P \subseteq B P P$ , then

A M = B P \cdot N P \subseteq B P \cdot B P P = B P P = A

Therefore

A M = M A

EX 2: ABBP: Alternating BPP

We’ve shown that

\underset{fixed number}{\underset{⏟}{A M \dots A M}} \subseteq A M

A B P P = \underset{number depends on the i n p u t}{\underset{⏟}{A M \dots A M}}

N P \subseteq A M_{p s}

A M_{p s} \subseteq N P

$M^{'}$ :

input: $x$
guess $r, y$ of poly size wrt $| x |$
execute $y^{'} = A (x, r)$
accept if $x # r # y’ # y ∈ D$

Proof: $\exists M$ s.t.

if $x \in L$ , $ℙ_{r} (x # r # A (x, r) # M (_) \in D)$

There exists $r$ s.t. $ℙ(x # r # A(x,r) # M(_) ∈ D) ≥ 1-\frac 1 {2^l}$

There exists $y ≝ M (_{)}$ s.t. $ℙ(x # r # A(x,r) # y ∈ D)≥ 1-\frac 1 {2^l}$

So there exists $r, y$ s.t. $M^{'}$ accepts
if $x \notin L$ , $∀M, ℙ_r(x # r # A(x, r) # M(_)∈ D) = 0$

The number of random coins is finite, so:

\forall M, \forall r, x # r #_\notin D

For $M$ constantly equal to $y$ :

\forall r, x # r # A (x, r) # y \notin D

so:

\forall y, \forall r,_\notin D

So $M^{'}$ almost accepts

x \in L ⟺ M^{'} accepts ⋮

EX 3: Polynomial Identity Testing

1.

To represent $X^{2^{n}}$

one only needs $n$ nodes.

2.

Given $S ≝ ⟦ 1, 10 \times 2^{m} ⟧ \subseteq ℤ$

Algorithm:

Draw (x_1, ⋯, x_n)∈S^n at random
Evaluate the circuit C
If C(x_1, ⋯, x_n ≠0):
    reject
else:
    accept

$C$ is a cicruit associated with polynomial $p$ .

If $p = 0$ :

ℙ (p (x_{1}, \dots, x_{n}) = 0) = 1 ⟶ OK

If $p \neq 0$ :

ℙ (p (x_{1}, \dots, x_{n}) = 0) \leq \frac{d | S |^{n - 1}}{| S |^{n}} = \frac{d}{| S |} = \frac{1}{10}

TD 12

EX 1

$P P$ :

if $x \in L$ , $ℙ ((x, r) = ⊤) > \frac{1}{2}$
if $x \notin L$ , $ℙ ((x, r) = ⊤) \leq \frac{1}{2}$

NB: if you ask $ℙ ((x, r) = ⊤) \geq \frac{1}{2}$ in the first condition, then all problems are recognized (guess randomly).

$P P_{1 / 2}$ :

if $x \in L$ , $ℙ ((x, r) = ⊤) \geq \frac{1}{2}$
if $x \notin L$ , $ℙ ((x, r) = ⊤) < \frac{1}{2}$

Considering a machine whose accepting and rejecting states have been inverted: $P P_{1 / 2} = P P$

and $P P$ is closed under complementation.

Every random machine is has a $P P$ way of accepting.

$N P = R P^{*}$ :

if $x \in L$ , $ℙ ((x, r) = ⊤) > 0$
if $x \notin L$ , $ℙ ((x, r) = ⊤) = 0$

Share on

Twitter Facebook Google+ LinkedIn