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