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.

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 miniatura|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.

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.

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 La classe BPP és tancada pel complement, la unió i la intersecció.

Referències

Categoria:Complexitat computacional Categoria:Classes de complexitat