Siguiente: Complejidad de Kolmogorov Un nivel arriba: Máquinas probabilísticas Anterior: .

Algunas inclusiones entre clases

Definamos

$$\mbox{\it ZPP}=R\cap\mbox{\rm co-{\em R}}.$$

Recordamos que un algoritmo en R es de Monte-Carlo: Ante respuestas afirmativas contesta afirmativamente, pero ante respuestas negativas puede contestar afirmativamente, aunque con probabilidades mínimas. Un algoritmo de tipo Las Vegas es tal que nunca miente: Ante respuestas afirmativas contesta afirmativamente, pero ante respuestas negativas contesta que no puede probar valores afirmativos. Los algoritmos de la clase ZPP son del tipo Las Vegas. Se tiene entonces las inclusiones siguientes:

$$\begin{array}{ccccccccc} P & \subset &\mbox{\it ZPP} & \subs... ...set & \mbox{\it PP} & \subset & \mbox{\it PSPACE} \end{array}$$