Siguiente: . Un nivel arriba: Máquinas-p Anterior: .

.

Sea

$$\mbox{\it PP}=\{L\vert\exists M\in \mbox{\rm $\frac{1}{2}$-mTp's}:L=L(M)\}.$$

Se tiene entonces la inclusión

$$\mbox{\it NP}\cup\mbox{\rm co-{\em NP}}\subset \mbox{\it PP}\subset \mbox{\it PSPACE}.$$