V teoretické informatice , přesněji v teorii složitosti , je věta Sipser-Gács-Lautemann (nebo Sipser-Lautemann nebo Sipser-Gácsova věta ) teorém, který uvádí, že pravděpodobnostní třída BPP ( pravděpodobnostní polynomiální čas s omezenou chybou) je zahrnuta v polynom hierarchie . Tento inkluzní vztah je překvapivý Protože definice polynomiální hierarchie neodkazuje na teorii pravděpodobností .
Sipser - Gács - Lautemannova věta - Třída složitosti BPP je obsažena v polynomiální hierarchii ( PH ) přesněji v Σ 2 ∩ Π 2
Třída BPP obsahuje přesně ty problémy, o nichž „téměř“ rozhoduje pravděpodobnostní Turingův stroj v polynomiálním čase v následujícím smyslu: stroj se mýlí s pravděpodobností menší než 1/3. Třída Σ 2 obsahuje problémy, o kterých rozhoduje deterministický polynomický Turingův stroj, který používá NP věštec.
Michael Sipser v roce 1983 ukázal, že BPP byl zahrnut do polynomiální hierarchie. Péter Gács mu ukázal, že BPP byl ve skutečnosti zahrnut v . A nakonec Clemens Lautemann podal jednodušší důkaz tohoto posledního výsledku.
V této části předvedeme demonstraci podle příslušné kapitoly v knize Teorie výpočtu od Kozena. Jelikož je BPP uzavřen doplňkově, stačí ukázat, že je BPP zahrnut do . Amplifikačním lemmatem dokazujeme, že opakováním provádění stroje M můžeme exponenciálně snížit pravděpodobnost chyby. Poté se vrátíme k existenci certifikátu, který zaručuje opravu určitého věštce.
Ve skutečnosti máme silnější inkluze s mezilehlými třídami:
kde MA je třída složitosti založená na protokolu Arthur a Merlin a je základní třídou symetrické hierarchie .
(en) Sanjeev Arora a Boaz Barak , Výpočetní složitost: moderní přístup , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , kap. 7.5.2 („BPP je v PH“)