Exercises 10: BPP, AM protocols, AM hierarchy

EX0: BPP-completeness

1.

\[L ≝ \lbrace (M, x, 1^t) \mid M \text{ accepts on input } x\text{ in time at most }t \rbrace\]

is $NP$-complete

$∈ NP$

1. check that the input is of the form $(M, x, 1^t)$
2. execute $M$ on $x$
3. … while at the same time keeping a timeout

EX3: The BP-operator

$B ≼_r C$

iff $∃ M; ∀x, ℙ(B(M(x)) = C(x)) ≥ \frac 2 3$

$L ∈ BP \cdot 𝒞$:

iff $∃ M \text{ and } D ∈ 𝒞$ s.t.

• $ℙ(M(x, r) ∈ D) ≥ \frac 2 3$ if $x∈L$
• $ℙ(M(x, r) ∉ D) ≥ \frac 2 3$ if $x∉L$

1.

Show that \(\lbrace L \mid L ≼_r L' \text{ for } L'∈𝒞 \rbrace = BP \cdot 𝒞\)

Let $L$ s.t. $∃L’∈ 𝒞$ s.t. $L ≼_r L’$

There exists $M$ s.t. for all $x$,

\[p_x ≝ ℙ(L'(M(x, r)) = L(x)) ≥ \frac 2 3\]

• $p_x = ℙ(M(x, r) ∈ L’) ≥ \frac 2 3$ if $x∈L$
• $p_x = ℙ(M(x, r) ∉ L’) ≥ \frac 2 3$ if $x∉L$

2. BPP is closed under polynomial-time randomized reduction

If $𝒞 ∈ BPP$, and $𝒞’ ≼ 𝒞$, then $𝒞’ ∈ BPP$

\[ℙ(𝒞(M(x, r)) = 𝒞'(x)) ≥ \frac 2 3\]

Let $M_{𝒞, ε}$ be the PTM recognizing $𝒞$ with proba $≥ε$

Let $x ∈ Σ^\ast_{𝒞’}$. We run

\[M_{𝒞, ε}(M(x, r_1), r_2)\]

$x ∉ 𝒞’$: \(p_ε = ℙ(M_{𝒞, ε}(M(x, r_1), r_2) = 1) ≤ \frac 1 3 + ε\)

Let $ε ≝ \frac 1 {12}$, then \(p_ε ≤ \frac 5 {12} < \frac 1 2\)

3.

Composition of reductions.

Suppose $A ≼_r B$ and $B ≼_r C$.

Let $M_1, M_2$, $r_1, r_2$ given by the definition.

• $ℙ(C(M_1(x, r)) ≠ B(x)) ≤ ε_1$
• $ℙ(B(M_1(x, r)) ≠ A(x)) ≤ ε_2$

If $x ∈ L_A$,

\[ℙ(B(M_1(x, r)) = 0) ≤ ε_2 + ε_1\]

EX 4: The class $BP \cdot NP$

1. $BP \cdot P = BPP$

$L ∈ BP \cdot P$:

iff $∃ M \text{ PTM and } D ∈ P$ s.t.

• $ℙ(M(x, r) ∈ D) ≥ \frac 2 3$ if $x∈L$
• $ℙ(M(x, r) ∉ D) ≥ \frac 2 3$ if $x∉L$

i.e $L ∈ BPP$

2. $BP \cdot NP = AM$

$⊆$

If $L ∈ \textbf{AM}$. Let $(A, M, D)$ given by the definition.

Let \(D' = \lbrace x \mid ∃y. x \# y ∈ D\rbrace\)

NB: It is implicitly assumed that $\vert y \vert$ is polynomial in $\vert x \vert$.

$D’ ∈ NP$ by definition of $NP$ by certificate.

• if $x ∈ L$: \(ℙ(A(x, r) ∈ D') = ℙ(∃y. A(x, r) \# y ∈ D) \\ ≥ ℙ(A(x, r) \# M(A(x, r))) ≥ 1 - \frac 1 {2^{n^l}}\)

• if $x ∉ L$: \(ℙ(A(x, r) ∉ D') = ℙ(∀y. A(x, r) \# y ∉ D) ≤ 1 - \frac 1 {2^{n^l}}\)

4.

$BPP ⊆ Σ_2$

If $x∈L$ ⟺

\[∃ t_0, ⋯, t_{q(n)/r}; ∀r, \bigvee_i M(x, r \oplus t_i) = \top\] \[∀n, ∃r_n, ∀x \text{ of len } n, M(x, r_n) \text{ not wrong}\]

$BPP ⊆ P/poly$