Por BPP / linear, refiro-me a máquinas de BPP com orientação linear, que cumprem a promessa quando recebem a orientação "correta", e a derandomização deve nos fornecer, digamos, um algoritmo P / linear ou (SUBEXP / linear).
Se usarmos suposições não uniformes, acho que os resultados clássicos devem funcionar, porque podemos "enganar" adversários não uniformes.
No entanto, usando suposições uniformes, digamos , a des randomização não trivial parece ser uma pergunta mais difícil.
Existem resultados para esse tipo de classe, não é necessário BPP / linear?
fonte