Релятивизируется ли псевдослучайный генератор Нисана?

16

Нисан доказал в «Псевдослучайных генераторах для пространственно-ограниченных вычислений», что существует псевдослучайный генератор, который «обманывает» ограниченные в пространстве вычисления. Эта конструкция справедлива для каждого оракула (по крайней мере, для неадаптивных запросов)?

Себастьян Бен Даниэль
источник
Я не могу ответить на этот вопрос, но хочу указать на статью под названием «Твердость против случайности» ( dx.doi.org/10.1016/S0022-0000(05)80043-1 ), которая может оказаться полезной.
MS Dousti 16.10.10

Ответы:

18

Это зависит от того, ограничена ли в вашем определении Oracle TM лента запросов оракула логарифмическим размером: если она ограничена, то PRG дурачит также L ^ A для любого A, если он не ограничен, то A может содержит список «псевдослучайных строк» ​​и, таким образом, L ^ A не будет одурачен.

Ноам
источник
Это верно для всех псевдослучайных генераторов, однако, например, генератор NW делает релятивизацию, если мы примем жесткость против оракула, которого мы хотим обмануть. Мне было интересно, можем ли мы сделать что-то подобное и для этого генератора.
Себастьян Бен Даниэль
5
Поскольку этот PRG полностью указан (то есть не основан на какой-то другой «жесткой функции f»), неясно, как использовать оракула в релятивизированной настройке.
Noam