Par BPP / linéaire, je me réfère aux machines BPP avec conseil linéaire, qui remplissent la promesse quand on leur donne le conseil "correct", et la dérandomisation devrait nous donner, disons, un algorithme P / linéaire ou (SUBEXP / linéaire).
Si nous utilisons des hypothèses non uniformes, je pense que les résultats classiques devraient fonctionner, car nous pouvons "tromper" les adversaires non uniformes.
Cependant, en utilisant des hypothèses uniformes, disons , la dérandomisation non triviale semble être une question plus difficile.
Existe-t-il des résultats concernant ce type de classes, pas nécessaire BPP / linéaire?
la source