Siguiente: Computabilidad con mTp's Un nivel arriba: Máquinas-p Anterior: .

.

Observaciones: 1. Probar que un problema está en R o en BPP es tan bueno como probarlo en P pues iterando el procedimiento de decisión se puede minimizar tanto cuanto se quiera la probabilidad de error sin aumentar por esto el tiempo polinomial de solución. 2. A la fecha no se conocen problemas completos en las clases R y BPP.