¿Se ha estudiado la des aleatorización de clases ligeramente no uniformes, por ejemplo, BPP / lineal?

10

Por BPP / lineal, me refiero a máquinas BPP con asesoramiento lineal, que cumple la promesa cuando se le da el consejo "correcto", y la desrandomización debería darnos, por ejemplo, un algoritmo P / lineal o (SUBEXP / lineal).

Si usamos suposiciones no uniformes, creo que los resultados clásicos deberían funcionar, porque podemos "engañar" a los adversarios no uniformes.

Sin embargo, usando suposiciones uniformes, digamos , la desrandomización no trivial parece una pregunta más difícil.miXPAGsiPAGPAG

¿Existen resultados con respecto a este tipo de clases, no necesariamente BPP / lineal?

Sebastian Ben Daniel
fuente

Respuestas: