# 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

Tags:

Updated: