Sipser – Lautemannova věta - Sipser–Lautemann theorem

v teorie výpočetní složitosti, Sipser – Lautemannova věta nebo Sipser – Gács – Lautemannova věta tvrdí, že pravděpodobnostní polynom s omezenou chybou (BPP) čas je obsažen v polynomiální časová hierarchie a konkrétněji Σ₂ ∩ Π₂.

V roce 1983 Michael Sipser ukázal, že BPP je obsažen v polynomiální časová hierarchie.^[1] Péter Gács ukázal, že BPP je ve skutečnosti obsažen v Σ₂ ∩ Π₂. Clemens Lautemann přispěl poskytnutím jednoduchého dokladu o členství BPP v Σ₂ ∩ Π₂, také v roce 1983.^[2] Předpokládá se, že ve skutečnosti BPP =P, což je mnohem silnější výrok než Sipser-Lautemannova věta.

Důkaz

Zde uvádíme Lautemannův důkaz.^[2] Bez ztráty obecnosti stroj M ∈ BPP s chybou ≤ 2^−|X| lze zvolit. (Všechny problémy BPP lze zesílit, aby se exponenciálně snížila pravděpodobnost chyby.) Základní myšlenkou důkazu je definování Σ₂ věta, která se rovná tvrzení, že X je v jazyce, L, definován M pomocí sady transformací vstupů náhodných proměnných.

Od výstupu M závisí na náhodném vstupu i na vstupu X, je užitečné definovat, které náhodné řetězce vytvářejí správný výstup A(X) = {r | M(X,r) přijímá}. Klíčem k důkazu je poznamenat, že když X ∈ L, A(X) je velmi velký a kdy X ∉ L, A(X) je velmi malý. Používáním bitová parita, ⊕, lze sadu transformací definovat jako A(X) ⊕ t={r ⊕ t | r ∈ A(X)}. První hlavní lemma důkazu ukazuje, že spojení malého konečného počtu těchto transformací bude obsahovat celý prostor náhodných vstupních řetězců. Použitím této skutečnosti a₂ věta a Π₂ lze vygenerovat větu, která je pravdivá právě tehdy X ∈ L (viz závěr).

Lemma 1

Obecnou myšlenkou prvního lemmatu je dokázat, že pokud A(X) pokrývá velkou část náhodného prostoru ${ displaystyle R = {1,0 } ^ {| r |}}$ pak existuje malá sada překladů, které pokryjí celý náhodný prostor. Ve více matematickém jazyce:

Li ${ displaystyle { frac {| A (x) |} {| R |}} geq 1 - { frac {1} {2 ^ {| x |}}}}$, pak ${ displaystyle existuje t_ {1}, t_ {2}, ldots, t_ {| r |}}$, kde ${ displaystyle t_ {i} in {1,0 } ^ {| r |}}$ takhle ${ displaystyle bigcup _ {i} A (x) oplus t_ {i} = R.}$

Důkaz. Náhodně vybrat t₁, t₂, ..., t_|r|. Nechat ${ displaystyle S = bigcup _ {i} A (x) oplus t_ {i}}$ (spojení všech transformací A(X)).

Takže pro všechny r v R,

${ displaystyle Pr [r notin S] = Pr [r notin A (x) oplus t_ {1}] cdot Pr [r notin A (x) oplus t_ {2}] cdots Pr [r notin A (x) oplus t_ {| r |}] leq { frac {1} {2 ^ {| x | cdot | r |}}}.}$

Pravděpodobnost, že v něm bude existovat alespoň jeden prvek R ne v S je

${ displaystyle Pr { Bigl [} bigvee _ {i} (r_ {i} notin S) { Bigr]} leq sum _ {i} { frac {1} {2 ^ {| x | cdot | r |}}} = { frac {2 ^ {| r |}} {2 ^ {| x | cdot | r |}}} <1.}$

Proto

${ displaystyle Pr [S = R] geq 1 - { frac {2 ^ {| r |}} {2 ^ {| x | cdot | r |}}}> 0.}$

Pro každého tedy existuje výběr ${ displaystyle t_ {1}, t_ {2}, ldots, t_ {| r |}}$ takhle

${ displaystyle bigcup _ {i} A (x) oplus t_ {i} = R.}$

Lemma 2

To ukazuje předchozí lemma A(X) může pokrýt každý možný bod v prostoru pomocí malé sady překladů. Doplňující k tomu, pro X ∉ L pouze malá část prostoru je pokryta ${ displaystyle S = bigcup _ {i} A (x) oplus t_ {i}}$. My máme:

${ displaystyle { frac {| S |} {| R |}} leq | r | cdot { frac {| A (x) |} {| R |}} leq | r | cdot 2 ^ {- | x |} <1}$

protože ${ displaystyle | r |}$ je polynom v ${ displaystyle | x |}$.

Závěr

Lemata ukazují, že jazykovou příslušnost k jazyku v BPP lze vyjádřit jako Σ₂ výraz, následovně.

${ displaystyle x v L iff existuje t_ {1}, t_ {2}, tečky, t_ {| r |} , forall r in R bigvee _ {1 leq i leq | r |} (M (x, r oplus t_ {i}) { text {přijímá}}).}$

To znamená X je v jazyce L jen kdyby existovaly ${ displaystyle | r |}$ binární vektory, kde pro všechny náhodné bitové vektory rTM M přijímá alespoň jeden náhodný vektor ⊕ t_i.

Výše uvedený výraz je v Σ₂ v tom, že je to nejprve existenciálně, pak všeobecně kvantifikováno. Proto BPP ⊆ Σ₂. Protože BPP je uzavřen pod doplněk, to dokazuje BPP ⊆ Σ₂ ∩ Π₂.

Silnější verze

Věta může být posílena na ${ displaystyle { mathsf {BPP}} subseteq { mathsf {MA}} subseteq { mathsf {S}} _ {2} ^ {P} subseteq Sigma _ {2} cap Pi _ { 2}}$ (vidět MA, S^P
₂ ).^[3][4]

Reference