Exercises 11: BPP, ABPP, PP

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}\]

TD 12

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\)

Leave a comment