Exercises 12: Review

NP, coNP

  • coNP: you can’t just take the opposite the NP machine, because the negation of an existential condition is not existential.

NP problems

General $NP$ problem $L, M, p$

  • Data: $x ∈ Σ^\ast$
  • Question: there exists a run $r$ s.t. $M(x) ⟶^r accept$

SAT:

  • Data: $φ ≝ \bigwedge_k C_k$ a boolean formula in CNF

  • Question: $∃ v$ s.t. $v ⊨ φ$

Cook-Levin in full form:

We have a bijection between runs of ND TM in poly time and valuation satisfying the Cook-Levin formula

  • $f: M, x ⟼ φ$
  • $g: r ⟼ v$
  • $M, x ⟼^r accept ⟺ g(r) ⊨ φ$

Oracles

  • the language $A^B$: $A$ (a set of TM) oracle $B$ (a language)

  • $A^E = \bigcup_{L∈E} A^L$

\[coSAT ∈ P^{SAT}\]

since you can complement what the oracle says.

Similarly, as $Π_{n-1} = coΣ_{n-1}$:

\[NP^{Σ_{n-1}} = NP^{Π_{n-1}}\]

NB: The usefulness of oracles is:

  • the repetition (ex: $P^{BPP} = BPP$: BPP repeated a polynomial number of times)
  • the fact that wa can complement

Polynomial Hierarchy (PH)

  • $Σ_n = NP^{Σ_{n-1}}$
  • $Π_n = (coNP)^{Σ_{n-1}}$
\[L ∈ Σ_n ⟺ ∃ L' ∈ Π_{n-1} s.t. L = \lbrace x \mid ∃y \text{ of poly size s.t. } x \# y ∈ L' \rbrace\]
Complete problem for $Σ_n$:

SAT of formulas of the form $\underbrace{∃, ∀, ∃, ⋯}_{n \text { alternances}}, F$

QBF:

PSPACE-complete

NB: If there is a problem PH-complete, then PH collapses since this problem is in one set of the PH

RP

$L ∈ RP$:

$x∈Σ^\ast$

  1. $x∈L ⟹ ℙ_r(M(x, r) = ⊥) < 1/2$
  2. $x∉L ⟹ ℙ_r(M(x, r) = ⊤) = 0$

  1. False negative

  2. Yes Means Yes:

    \[∃r; M(x, r) = ⊤ \underbrace{⟺}_{\text{ because finite event proba}} ℙ_r(M(x, r) = ⊤) ≠ 0 ⟹ x∈L\]

NB: Here, because of the cylinder proba, the equivalence is true even if we have infinite events.

$L ∈ NP$:

$x∈Σ^\ast$

  1. $x∈L ⟹ ∃y; M(x, y) = ⊤$
  2. $x∉L ⟹ ∀y; M(x, y) = ⊥$

So

$L ∈ NP = RP^\star$ (biggest error):

$x∈Σ^\ast$

  1. $x∈L ⟹ ∃y; M(x, y) < 1$
  2. $x∉L ⟹ ∀y; M(x, y) = 0$
\[PH ⊆ PSPACE\\ AM ⊆ ABPP\]

ZPP

\[ZPP = RP ∩ coRP\] \[ZPP = \underbrace{P_{ExpectedTIME}}_{\text{ mean execution time is polynomial}}\]

Run the two MT $M_1 ∈ RP, M_2 ∈ coRP$ in parallel

$L ∈ PP$:

$x∈Σ^\ast$

  1. $x∈L ⟹ ℙ_r(M(x, r) = ⊥) < 1/2$
  2. $x∉L ⟹ ℙ_r(M(x, r) = ⊤) ≤ 1/2$

NB:

  1. $x∈L ⟹ ℙ_r(M(x, r) = ⊥) ≤ 1/2$
  2. $x∉L ⟹ ℙ_r(M(x, r) = ⊤) ≤ 1/2$

is everything, since you can just take the MT that returns yes or no according to a Bernoulli scheme of parameter $1/2$

BPP ⟶ semantic class, not syntaxic. Because we can’t check that our MT indeed respect the proba

  • $M=NP$
  • $BPP = A$ (same condition)

Warning: the forall doesn’t come out easily (contrary to the “there exists”).

$BP\cdot NP = AM$ (same condition on Merlin)

$AM^{BPP}$

$BPP ⊆ P/poly$

P/poly: MT poly that resorts to a circuit $x ⟼ C_{\vert x \vert}(x)$ whose size depend on $x$ (the function that gives circuits is non computable!)

$x, r$, then thanks to BPP properties: for all $n$, there exists $r_n$ s.t. for all $x$ of size $n$, $M(x, r_n)$ is right (if $x∈L$, true, else false)

$M(\cdot, r_n)$ becomes our $c_n$

\[R_x = \lbrace x \mid M(x, r) = ⊤ \rbrace\]

A MT and a formula = same thing A MT and a circuit = same thing since circuit is a formula

Page 10:

\[BPP ⊆ Σ_2 ∩ Π_2\]

If $R_x$ is huge, there exists $t_1, ⋯, t_n$ s.t. $\bigcup t_i \oplus R_x = Σ^\ast$

Look at Fingerprint exercise

Leave a comment