La dérandomisation de classes légèrement non uniformes, par exemple BPP / linéaire, a-t-elle été étudiée?

10

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.EXPBPP

Existe-t-il des résultats concernant ce type de classes, pas nécessaire BPP / linéaire?

Sebastian Ben Daniel
la source

Réponses: