A des randomização de classes ligeiramente não uniformes, por exemplo, BPP / linear, foi estudada?

10

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

Existem resultados para esse tipo de classe, não é necessário BPP / linear?

Sebastian Ben Daniel
fonte

Respostas:

5

Eu usei a pesquisa deste acadêmico , e o único resultado que parece relevante de alguma forma é o seguinte:

Lance Fortnow, Adam Klivans, Conselho Linear para Espaço Logarítmico Aleatório, ECCC TR05-042, 2005.

Infelizmente, acho que não é exatamente o que você precisa. Em particular, o principal resultado do trabalho é . No entanto, acredito que as técnicas utilizadas podem ser úteis no caso de sua pergunta.RLL/O(n)

MS Dousti
fonte