En teoria de la complexitat, la classe de complexitat PP é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 menor de 1/2 per totes les instàncies.^[1][2]

Si un problema de decisió és a PP, llavors hi ha un algorisme per ell que permet prendre decisions aleatòries, es garanteix que funciona durant un temps polinòmic i si la resposta és SI, l'algorisme donarà SI amb una probabilitat més gran de 1/2. Si la resposta és NO, l'algorisme respondrà SI amb una probabilitat menor de 1/2. En termes pràctics, aquesta classe és la dels problemes que poden ser resolts fins a qualsevol precisió executant un algorisme aleatori un nombre suficient de vegades.

Una definició alternativa és dir que la classe PP és la que formen tots els problemes de decisió que es poden resoldre per una màquina de Turing no determinista en tempos polinòmic i que la condició d'acceptació és que la majoria de camins d'execució accepten. Per aquest motiu alguns autors suggereixen el nom Majority-P.^[3]

Un llenguatge L és a PP si i només si existeix una màquina de Turing probabilista M tal que

• M funciona un temps polinòmic per totes les entrades
• per tot x a L, M treu 1 amb probabilitat estrictament més gran que 1/2
• per tot x no a L, M treu 0 amb probabilitat menor o igual a 1/2

Es pot definir de forma alternativa usant només màquines de Turing deterministes. Un llenguatge L és a PP si i només si existeix una màquina de Turing determinista i un polinomi p tal que

• M funciona en temps polinòmic per totes les entrades
• per tot x a L, la fracció de cadenes y de longitud p(|x|) que satisfà M(x,y) = 1 és estrictament més gran que 1/2
• per tot x no a L, la fracció de cadenes y de longitud p(|x|) que satisfà M(x,y) = 1 és menor o igual a 1/2

En ambdues definicions, es pot canviar "menor o igual a" per "menor que" i el llindar d'1/2 per qualsevol nombre racional entre (0,1) sense canviar la classe.

PP conté BPP, ja que els algorismes probabilístics descrits a la definició de BPP formen una subclasse dels algorismes de la definició de PP.

PP també conte la classe NP, Això es prova veient que els problema NP-complet de satisfacibilitat (SAT) pertanyen a PP. Com que NP-complet està dins de NP, i es pot reduir qualsevol problema polinòmic a PP, NP és dins de NP. A més, com que PP és tancat respecte el complement, co-NP també és dins de PP.

Per tant, PP conté també a MA.

Es pot demostra també que PP conté la classe BQP. I es pot provar que PP és igual a la classe postBQP (BQP amb postselecció).

Per totes aquestes inclusions, PP conté QMA, que agrupa les inclusions de MA i BQP.

PP està continguda dins de PSPACE.