Vikipedio:Projekto matematiko/BPP
El Vikipedio
 |
Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al BPP (eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi. |
- Ĉi tiu artikolo estas pri la komplekseca klaso. Por la Nigra naciisma organizo, vidu Nigra Pantero Festi.
En komplikteorio, BPP estas la klaso de decid-problemoj solvebla per probableca maŝino de Turing en polinoma tempo, kun erar-probablo de maksimume 1/3 por ĉiuj aper(aĵ)oj. La mallongigo BPP estas de Bounded-eraro (anglaĵo signifanta "barhava"), Probableca, Polinomia tempo.
| BPP algoritmo (1 kuri) | ||
|---|---|---|
| Respondo produktita | ||
| Ĝusta respondo |
JES | NE |
| _YES_ | ≥2/3 | ≤1/3 |
| No | ≤1/3 | ≥2/3 |
| BPP algoritmo (n (kuras, rulas)) | ||
| Respondo produktita | ||
| Ĝusta respondo |
_YES_ | No |
| _YES_ | > 1-e-n/18 | < e-n/18 |
| No | < e-n/18 | > 1-e-n/18 |
Se problemo estas en BPP, tiam estas algoritmo por ĝi, kiu estas permesita klaki monerojn kaj fari hazardaj decidojn. Ĝi estas garantiita kuri en polinoma tempo. Sur iu ajn donita kuro de la algoritmo, ĝi havas probablecon de maksimume 1/3 doni la eraran respondo. Tio estas vera, ĉu la respondo estas _YES_ aŭ No.
La elekto de 1/3 en la difino estas ajna. Ĝi povas esti iu ajn konstanto inter 0 kaj 1/2 ekskluzivitaj kaj la aro BPP estos neŝanĝita; tamen, tiu konstanto devas esti sendependa de la enigo. La ideo estas, ke estas probablo de eraro, sed se la algoritmo estas kurita multajn fojojn, la ŝanco, ke la plejparto de la kuroj estas eraraj forfalas eksponente sekve de tio de la Baro de Ĉernov [1]. Ĉi tiu faras ĝin pova krei alte precizan algoritmon per nure kuri la algoritmo kelkfoje kaj prenante "plejparto (baloti, baloto, balotado, voĉi, voĉdoni, voĉo)" de la respondoj.
BPP estas unu el la plej granda praktika klasoj de problemoj, kio signifas, ke plej problemoj de intereso en BPP havas kompetentajn probablecajn algoritmojn, kiuj povas esti kuritaj rapide sur realaj modernaj (maŝinoj, aparatoj), per la maniero priskribita pli supre. Pro ĉi tiu kaŭzo estas de granda praktika intereso kiuj problemoj kaj klasoj de problemoj estas en BPP.
Enhavo |
[redaktu] Interrilato al aliaj kompleksecaj klasoj
Estas sciate, ke BPP estas fermita sub komplemento; tio estas, BPP=Co-BPP. Estas malfermita demando, ĉu BPP estas subaro de NP. Estas ankaŭ malfermita demando ĉu NP estas subaro de BPP; se ĝi estas, tiam NP=RP kaj PH (kemia parametro) 
BPP([2]) (multaj konsideras ĉi tion malverŝajna, ĉar ĝi devus enhavi praktikajn solvaĵojn por limigo de malfacila NP-kompleteco problemoj, problemoj). Estas sciate, ke RP estas subaro de BPP, kaj BPP estas subaro de PP. Ne estas sciate ĉu tiuj du estas severa, subaroj. BPP estas enhavita en PH (kemia parametro).
La ekzisto de certaj fortaj pseŭdohazardaj nombraj generiloj estas konjektita de plej kompetentuloj de la kampo. Ĉi tiu konjekto implicas, ke hazardo ne donas aldonan komputan povon al polinoma tempa kalkulado, tio estas, P=RP=BPP. Notu, ke ordinaraj generiloj estas ne sufiĉaj por montri ĉi tiu rezulto; iu ajn probableca algoritmo realigita uzante tipa hazarda nombra generilo kun fiksita semo ĉiam produktos malĝustajn rezultojn sur certa enigoj (kvankam ĉi tiuj enigoj povus esti maloftaj). Ni ankaŭ havas ke P = BPP se EXPTIME kolapsas al Ma (Babai, k.a.), se la eksponenta funkcio-tempa hierarkio kolapsas al E = DTIME(2O(n)) (Babai, k.a.), aŭ se E havas eksponentan funkcian cirkvitan kompleksecon (Impagliazzo kaj Wigderson).
[redaktu] Aliaj propraĵoj
Delonge, unu de la plej famaj problemoj, kiuj estis sciataj al furori BPP sed ne sciata al furori P estis la problemo (determini, difini) ĉu donita nombro estas primo. Tamen, en la 2002 papero PRIMES estas en P, Manindra Agrawal kaj liaj studentoj Neeraj Kayal kaj Nitin Saxena fundamenti (determinisma, determina) polinomo-tempa algoritmo por ĉi tiu problemo, tial montranta, ke ĝi estas en P.
BPP estas malalta por sin, kio signifas, ke BPP-maŝino kun la povo solvi BPP-problemojn tujprete (BPP orakola maŝino) estas neniel pli pova ol la maŝino sen ĉi tiu superflua povo.
Ĉi tiu klaso estas difinita por ordinara Maŝino de Turing plus fonto de hazardo. La (koresponda, respektiva) klaso por kvantuma komputilo estas BQP.
Anaro en iu ajn lingvo en BPP povas esti difinita per polinomo-ampleksa bulea cirkvito (vidu [[cirkvita komplekseco]|cirkvitan kompleksecon]]).
[redaktu] Eksteraj ligoj
[redaktu] Referencoj
- László Babai, Lanco Fortnow, Noam Nisano, kaj Avi Wigderson (1993). "BPP havas simuladojn de _subexponential_ tempo se neniu EXPTIME havas eldoneblajn pruvojn". Komputa Komplekseco, 3:307–318.
- Russell Impagliazzo kaj Avi Wigderson (1997). "P=BPP se E postulas eksponentajn funkciajn cirkvitojn: _Derandomizing_ la XOR-Lemo". Paperoj de la Dudek-(Naŭto, Naŭno) Ĉiujara ACM-Simpozio sur Teorio de Komputanta, pp. 220–229.
- Valenteno Kabanets (2003). "CMPT 710 – Komplekseca Teorio: Prelego 16". Simon Fraser Universitato.
- Paĝoj 257–259 de sekcio 11.3: Hazarda (Fontoj, Fontas). Paĝoj 269–271 de sekcio 11.4: Cirkvita komplekseco.
- Sekcio 10.2.1: La klaso BPP, pp.336–339.
