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