Vés al contingut

BPP (complexitat)

De la Viquipèdia, l'enciclopèdia lliure

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]
Relació de BPP amb d'altres classes de complexitat probabilístiques.

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 PHBPP.[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]
  1. Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790. 
  2. Peter., Linz,. An introduction to formal languages and automata. 5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012. ISBN 9781449615529. 
  3. «Complexity Zoo:B - Complexity Zoo» (en anglès). Arxivat de l'original el 2013-06-03. [Consulta: 29 novembre 2018].
  4. «Pulling Out The Quantumness» (en anglès). [Consulta: 29 novembre 2018].