BPP (complexitat)
En teoria de la complexitat, la classe de complexitat BPP (bounded-error probabilistic polynomial time) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing probabilística en un temps polinòmic amb un error fitat de 1/2 per totes les instàncies. BPP és la classe més gran amb problemes pràctics, ja que molts problemes d'interès a BPP tenen algorismes probabilístics que poden ser executats en màquines modernes. BPP conté P, ja que una màquina determinista és un cas especial de màquina probabilística.[1][2]
Informalment, un problema és a BPP si hi ha un algorisme amb les següents propietats:
- pot prendre decisions aleatòries
- es garanteix que s'executa amb temps polinòmic
- a cada execució de l'algorisme, hi ha una probabilitat de com a molt 1/3 de donar la resposta incorrecta, ja sigui SI o NO.
Relació amb d'altres classes
[modifica]
Si es treu l'aleatorietat de la definició de BPP, s'obté la classe de complexitat P. Si a la definició es reemplaça la màquina de Turing ordinària per un computador quàntic s'obté la classe BQP.
Afegint postselecció a BPP o permetent que els camins de còmput tinguin diferents longituds dona la classe BPPpath Aquesta classe se sap que conté NP, i està continguda a la seva contrapart PostBQP.[3]
Se sap que BPP és tancada al complement, i per tant BPP = co-BPP. La relació entre BPP i NP no es coneix: no se sap si BPP és un subconjunt de NP, si NP és un subconjunt de BPP o no. Si NP està dins de BPP, cosa que es considera poc probable, ja que permetria solucions pràctiques per problemes NP-complets, llavors NP = RP i PH ⊆ BPP.[4]
Es coneix que RP és un subconjunt de BPP i BPP és un subconjunt de PP. No se sap si aquesta inclusió és estricta o no, ja que no es coneix si P és un subconjunt estricte de PSPACE. BPP està dins el segon nivell de la jerarquia polinòmica i per tant està continguda a PH.
Propietats de clausura
[modifica]La classe BPP és tancada pel complement, la unió i la intersecció.
Referències
[modifica]- ↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.
- ↑ Peter., Linz,. An introduction to formal languages and automata. 5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012. ISBN 9781449615529.
- ↑ «Complexity Zoo:B - Complexity Zoo» (en anglès). Arxivat de l'original el 2013-06-03. [Consulta: 29 novembre 2018].
- ↑ «Pulling Out The Quantumness» (en anglès). [Consulta: 29 novembre 2018].
| Considerades tractables | |
|---|---|
| Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
