BPP (karmaşıklık)

Olarak teorik bilgisayar biliminin spesifik olarak, karmaşıklık teorisi , BPP sınıfı ( sınırlı hatası olasılıksal polinom süresi) olduğu sınıf bir karar problemlerinin bir karar olasılıklı Turing makinası zamanlı polinoma cevap hatası bir olasılık ile, daha az 1/3 daha .

Tanım

İlk tanım

BPP sınıfı, aşağıdaki kabul koşullarını karşılayan polinom zamanda olasılıklı bir Turing makinesinin bulunduğu problemler kümesidir veya eşdeğer bir dil biçimidir :

Sözcük dilde değilse, makine onu 2 / 3'ten büyük bir olasılıkla reddeder.
Kelime dilde ise, makine bunu 2 / 3'ten büyük bir olasılıkla kabul eder.

Diğer bir deyişle, makine 1 / 3'ten az bir olasılıkla hatalı.

Resmi tanımlama

BPP sınıfını , herhangi bir kelime için bunu doğrulayan bir polinom ve bir dil olacak şekilde diller kümesi olarak tanımlarız : $L$ $p (n)$ ${{\ Rm {P}}} içinde bir \$ $x$

$x \ in L \ Rightarrow {\ underet {\ varepsilon \ in \ {0,1 \} ^ {{p (| x |)}}} {Pr}} ((x, \ varepsilon) \ in A) \ geq {\ frac {2} {3}}$ .
$x \ notin L \ Rightarrow {\ underet {\ varepsilon \ in \ {0,1 \} ^ {{p (| x |)}}} {Pr}} ((x, \ varepsilon) \ in A) \ leq {\ frac {1} {3}}$ .

Diğer sınıflarla ilişkiler

Deterministik ve olasılıklı polinom zamanı

Belirleyici bir hesaplama yapmak için olasılıklı bir makine ve dolayısıyla P BPP kullanabiliriz . Diğer dahil etme, açık bir sorudur. Daha genel bir ifadeyle, soru rasgeleliğin hesaplamayı hızlandırmak için yararlı olup olmadığını bilmektir. Karmaşıklık topluluğunun bu konuda bir fikri değişti: 1980'lere kadar çoğu araştırmacı BPP'nin P'den farklı olduğunu düşündü, sonra çeşitli sonuçlar bu inancı altüst etti. Bugün genellikle bir beraberlik düşünülmektedir. $\ scriptstyle \ subseteq$

Diğer ilişkiler

BPP ayrıca kabul koşulları daha güçlü ZPP , RP ve co-RP olan olasılık sınıflarını da içerir .

Polinom hiyerarşisinin notasyonları ile, Sipser - Gács - Lautemann teoremine göre var . $BPP \ subseteq \ Sigma _ {2} ^ {p} \ cap \ Pi _ {2} ^ {p}$

Boolean devre sınıfları dünyasında , Adleman'ın teoremi BPP P / poly'yi verir ( Adleman 1978 ). $\ scriptstyle \ subseteq$

Kuantum varyantı BPP olan BQP .

Özellikler ve teoremler

Gerekirse daha verimli makinelere sahip olabiliriz , yani sınıfı değiştirmeden 2 / 3'ünü ve 1 / 3'ünü (çok genç için) değiştirebiliriz. Bu destek, makineyi birkaç kez bağımsız olarak fırlatıp oy vererek yapılabilir. Hesaplama, Chernoff sınırlarını kullanır . $1- \ epsilon$ $\ epsilon$ $\ epsilon$

BPP tamamlayıcı tarafından kapatılır, yani BPP = co-BPP.

Tarih

Bu sınıf, RP ve ZPP sınıflarıyla aynı zamanda, olasılıklı Turing makinelerinin hesaplamalı karmaşıklığı makalesinde J. Gill tarafından tanıtıldı .

Kaynakça

(tr) Sanjeev Arora ve Boaz Barak , Hesaplamalı Karmaşıklık: Modern Bir Yaklaşım , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , böl. 7 ("Rastgele Hesaplama")
Leonard. M. Adleman , "Rastgele polinom zaman üzerine iki teorem" , Ondokuzuncu Yıllık IEEE Sempozyumu Bilgisayar Biliminin Temelleri Bildirilerinde ,1978, 75–83 s. ( DOI 10.1109 / SFCS.1978.37 )

Dış bağlantı

( fr ) Karmaşıklık Hayvanat Bahçesi'ndeki BPP sınıfı

Notlar ve referanslar

Sylvain Perifel , Algoritmik karmaşıklık , Elipsler ,2014, 432 s. ( ISBN 9782729886929 , çevrimiçi okuyun ) , böl. 12.1 ("Derandomizasyon")s. 318.
(in) Sanjeev Arora ve Boaz Barak , Hesaplamalı Karmaşıklık: Modern Bir Yaklaşım , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , böl. 7bölüm 5.2 BPP, PH içinde
Karmaşıklık Hayvanat Bahçesi
(inç) John Gill , " Olasılıklı Turing makinesinin hesaplamalı karmaşıklığı " , SIAM Journal we Computing , cilt. 6, n, O , 4, 1977, s. 675-695