next up previous contents
Siguiente: . Un nivel arriba: Máquinas-p Anterior: .

.

Sea

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

Se tiene entonces la inclusión

\begin{displaymath}\mbox{\it NP}\cup\mbox{\rm co-{\em NP}}\subset \mbox{\it PP}\subset \mbox{\it PSPACE}.\end{displaymath}



Guillermo Morales-Luna
2000-07-10