Исследована ли дерандомизация слегка неоднородных классов, например, BPP / linear?

10

Под BPP / linear я подразумеваю машины BPP с линейным советом, который выполняет обещание, когда дается «правильный» совет, и дерандомизация должна дать нам, скажем, P / линейный или (SUBEXP / линейный) алгоритм.

Если мы используем неоднородные предположения, я думаю, классические результаты должны работать, потому что мы можем «обмануть» неоднородных противников.

Однако, используя единообразные предположения, скажем, , нетривиальная дерандомизация кажется более сложным вопросом.ЕИкспВпп

Существуют ли результаты, касающиеся такого рода классов, не обязательно BPP / линейный?

Себастьян Бен Даниэль
источник

Ответы: