# Proofs to bear in mind

$BPP ⊆ P/poly$ main argument:

$∀n, ∃r_n, ∀x; \vert x \vert = n; M(x, r_n) \text{ is not wrong}$

$NP ⊆ P/poly ⟹ PH ⊆ P/poly$: see the formulas

Therefore: as $PH ⊆ P/poly$ implies that the polynomial hierarchy collapses, it follows that $NP ⊆ BPP$ is unlikely

$BPP ⊆ Σ_2 ∩ Π_2$
• $BPP ⊆ Σ_2$:

• $x ∈ L ∈ BPP ⟹ ∃t_0, ⋯, t_{m/n}; ∃ r; \bigwedge_i M(x, t_i \oplus r)$
• $x ∈ Σ^\ast$, Derandomization: $R_x = \lbrace r \mid M(x, r) = \top \rbrace$ If $R_x$ is huge, $∃t_0, ⋯, t_{m/n}$

# EX 1: NP and BPP

## 1.

If $P = NP$, then $PH = P$

Indeed, if $P = NP$, then $coNP = P = NP$, and $Σ_1 = Π_1 = Π_0 = Σ_0$

Therefore

$BPP ⊆ PH ⊆ P$

## 2.

If $NP ⊆ BPP$, then $AM = MA$

Wrong argument:

$A = BPP, M = NP$ ⟹ if $M ⊆ A$, then

• $MA ⊆ AA ⊆ A$
• $AM ⊆ AA ⊆ A$

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

  digraph {
rankdir=BT;
"ε = P" -> "M = NP", "A = BPP";
"M = NP" -> MA;
"A = BPP" -> "MA" -> "AM"
}


If $NP ⊆ BPP$, then

$AM = BP\cdot NP ⊆ BP\cdot BPP = BPP = A$

Therefore

$AM = MA$

# EX 2: ABBP: Alternating BPP

We’ve shown that

$\underbrace{AM ⋯ AM}_{\text{fixed number}} ⊆ AM$ $ABPP = \underbrace{AM ⋯ AM}_{\text{number depends on the }input}$
$NP ⊆ AM_{ps}$ $AM_{ps} ⊆ NP$

$M’$:

• input: $x$

• guess $r, y$ of poly size wrt $\vert x \vert$
• execute $y’= A(x,r)$
• accept if $x # r # y’ # y ∈ D$

Proof: $∃M$ s.t.

• if $x ∈ L$, $ℙ_r(x \# r \# A(x, r) \# M(\_) ∈ 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∉L$, $∀M, ℙ_r(x # r # A(x, r) # M(_)∈ D) = 0$

The number of random coins is finite, so:

$∀M, ∀r, x \# r \# \_ ∉ D$

For $M$ constantly equal to $y$:

$∀r, x \# r \# A(x, r) \# y ∉ D$

so:

$∀y, ∀r, \_ ∉ D$

So $M’$ almost accepts

$x ∈ L ⟺ M' \text{ accepts} \vdots$

# EX 3: Polynomial Identity Testing

## 1.

To represent $X^{2^n}$

  digraph {
rankdir=TB;
times2[label="×"];
"x" -> "×", "×";
"×" -> "⋮", "⋮";
"⋮" -> times2, times2;
}


one only needs $n$ nodes.

## 2.

Given $S ≝ ⟦1, 10 × 2^m⟧⊆ ℤ$

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, ⋯, x_n) = 0) = 1 ⟶ \text{ OK}$

If $p≠0$:

$ℙ(p(x_1, ⋯, x_n)=0) ≤ \frac{d \vert S \vert^{n-1}}{\vert S \vert^n} = \frac{d}{\vert S \vert} = \frac 1 {10}$

# EX 1

$PP$:

• if $x ∈ L$, $ℙ((x, r)= \top) > \frac 1 2$

• if $x ∉ L$, $ℙ((x, r)= \top) ≤ \frac 1 2$

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

$PP_{1/2}$:

• if $x ∈ L$, $ℙ((x, r)= \top) ≥ \frac 1 2$

• if $x ∉ L$, $ℙ((x, r)= \top) < \frac 1 2$

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

and $PP$ is closed under complementation.

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

$NP = RP^\ast$:

• if $x ∈ L$, $ℙ((x, r)= \top) > 0$

• if $x ∉ L$, $ℙ((x, r)= \top) = 0$

Tags:

Updated: