Sipser-Lautemann teoremasi - Sipser–Lautemann theorem

Yilda hisoblash murakkabligi nazariyasi, Sipser-Lautemann teoremasi yoki Sipser-Gács-Lautemann teoremasi ta'kidlaydi chegaralangan xato ehtimoliy polinom (BPP) vaqti polinom vaqt ierarxiyasi, va aniqroq Σ₂ ∩ Π₂.

1983 yilda, Maykl Sipser BPP ning tarkibida ekanligini ko'rsatdi polinom vaqt ierarxiyasi.^[1] Péter Gács BPP aslida Σ tarkibida ekanligini ko'rsatdi₂ ∩ Π₂. Klemens Lautemann BPP ga a'zo bo'lishining sodda dalillarini keltirib, o'z hissasini qo'shdi₂ ∩ Π₂, shuningdek, 1983 yilda.^[2] Aslida BPP = bo'lishi taxmin qilinmoqdaP, bu Sipser-Lautemann teoremasiga qaraganda ancha kuchli bayon.

Isbot

Bu erda biz Lautemannning dalillarini taqdim etamiz.^[2] Umumiylikni yo'qotmasdan, mashina M Error BPP xatosi bilan ≤ 2^−|x| tanlanishi mumkin. (Barcha BPP muammolari xatolik ehtimolini eksponentsial ravishda kamaytirish uchun kuchaytirilishi mumkin.) Dalilning asosiy g'oyasi - Σ ni aniqlash₂ buni bildirishga teng bo'lgan jumla x tilda, Ltomonidan belgilanadi M tasodifiy o'zgaruvchining kirishlarining konvertatsiya to'plamidan foydalangan holda.

Chiqishidan beri M kirish kabi tasodifiy kiritishga bog'liq x, qaysi tasodifiy satrlarning to'g'ri chiqishini aniqlab olish foydalidir A(x) = {r | M(x,r) qabul qiladi}. Isbotning kaliti qachon ekanligini ta'kidlashdir x ∈ L, A(x) juda katta va qachon x ∉ L, A(x) juda kichik. Foydalanish orqali bitlik tengligi, ⊕, transformatsiyalar to'plamini quyidagicha aniqlash mumkin A(x) ⊕ t={r ⊕ t | r ∈ A(x)}. Dalillarning birinchi asosiy lemmasi shuni ko'rsatadiki, ushbu transformalarning kichik sonli sonining birlashishi tasodifiy kirish satrlarining butun maydonini o'z ichiga oladi. Ushbu faktdan foydalanib, a₂ jumla va a Π₂ jumla hosil bo'lishi mumkin, agar u shunday bo'lsa va bu to'g'ri bo'lsa x ∈ L (xulosaga qarang).

Lemma 1

Lemmaning birinchi g'oyasi, agar ekanligini isbotlashdir A(x) tasodifiy maydonning katta qismini qamrab oladi ${ displaystyle R = {1,0 } ^ {| r |}}$ unda tasodifiy maydonni to'liq qamrab oladigan kichik tarjimalar to'plami mavjud. Ko'proq matematik tilda:

Agar ${ displaystyle { frac {| A (x) |} {| R |}} geq 1 - { frac {1} {2 ^ {| x |}}}}}$, keyin ${ displaystyle mavjud t_ {1}, t_ {2}, ldots, t_ {| r |}}$, qayerda ${ displaystyle t_ {i} in {1,0 } ^ {| r |}}$ shu kabi ${ displaystyle bigcup _ {i} A (x) oplus t_ {i} = R.}$

Isbot. Tasodifiy tanlash t₁, t₂, ..., t_|r|. Ruxsat bering ${ displaystyle S = bigcup _ {i} A (x) oplus t_ {i}}$ (barcha o'zgarishlarning birlashishi A(x)).

Shunday qilib, hamma uchun r yilda 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 |}}}.}$

Hech bo'lmaganda bitta element mavjud bo'lish ehtimoli R emas S bu

${ 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.}$

Shuning uchun

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

Shunday qilib, har biri uchun tanlov mavjud ${ displaystyle t_ {1}, t_ {2}, ldots, t_ {| r |}}$ shu kabi

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

Lemma 2

Oldingi lemma shuni ko'rsatadiki A(x) kichik tarjimalar to'plami yordamida kosmosdagi barcha mumkin bo'lgan nuqtalarni qamrab olishi mumkin. Bunga qo'shimcha, chunki x ∉ L bo'shliqning faqat kichik qismi qoplanadi ${ displaystyle S = bigcup _ {i} A (x) oplus t_ {i}}$. Bizda ... bor:

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

chunki ${ displaystyle | r |}$ in polinom hisoblanadi ${ displaystyle | x |}$.

Xulosa

Lemmalar shuni ko'rsatadiki, BPP da tilning tilga a'zoligi $ p $ sifatida ifodalanishi mumkin₂ ifoda, quyidagicha.

${ displaystyle x in L iff t_ {1}, t_ {2}, dots, t_ {| r |} , forall r in R bigvee _ {1 leq i leq | r mavjud |} (M (x, r oplus t_ {i}) { text {qabul qiladi}}).}$

Anavi, x tilda L agar mavjud bo'lsa ${ displaystyle | r |}$ ikkilik vektorlar, bu erda barcha tasodifiy bit vektorlar uchun r, TM M kamida bitta tasodifiy vektorni qabul qiladi t_men.

Yuqoridagi ibora Σ₂ u avval ekzistensial, so'ngra universal miqdor bilan belgilanadi. Shuning uchun BPP ⊆ Σ₂. BPP yopiq bo'lgani uchun to'ldiruvchi, bu BPP ⊆ Σ ekanligini tasdiqlaydi₂ ∩ Π₂.

Kuchli versiya

Teoremani kuchaytirish mumkin ${ displaystyle { mathsf {BPP}} subseteq { mathsf {MA}} subseteq { mathsf {S}} _ {2} ^ {P} subseteq Sigma _ {2} cap Pi _ { 2}}$ (qarang MA, S^P
₂ ).^[3][4]

Adabiyotlar