Нисан доказал в «Псевдослучайных генераторах для пространственно-ограниченных вычислений», что существует псевдослучайный генератор, который «обманывает» ограниченные в пространстве вычисления. Эта конструкция справедлива для каждого оракула (по крайней мере, для неадаптивных запросов)?
cc.complexity-theory
space-bounded
derandomization
Себастьян Бен Даниэль
источник
источник
Ответы:
Это зависит от того, ограничена ли в вашем определении Oracle TM лента запросов оракула логарифмическим размером: если она ограничена, то PRG дурачит также L ^ A для любого A, если он не ограничен, то A может содержит список «псевдослучайных строк» и, таким образом, L ^ A не будет одурачен.
источник