Какова мотивация определения псевдослучайного в Nisan / Wigderson?

Я читаю классическую «Твердость против случайности» Нисана и Вигдерсона. Пусть и исправим функцию . Они определяют семейство функций как псевдослучайное в случае, если для каждой схемы размера мы имеемl : N → N G = { G n : B l ( n ) → B n$B=\{0,1\}$$l\colon \mathbb{N} \to \mathbb{N}$$G = \{G_n : B^{l(n)} \to B^n\}$$n$

$(*) \ \ | P(C(x) = 1) - P(C(G(y))=1) | < 1/n$

(где - равномерные случайные величины).$x \in B^{n},y \in B^{l(n)}$

Я понимаю, что я должен думать о и как о случайных переменных, и что я хочу сравнить расстояние между и как случайные величины. Я понимаю, что схемы используются как своего рода «тесты», чтобы понять, можно ли «вычислить»Я действительно борюсь с тем, почему условие является правильным. Есть ли у кого-нибудь совет о том, как думать об этом определении?$x$$y$$x$$G(y)$$G$$(*)$

Есть два аспекта, которые необходимо упомянуть.

Первый - это общая идея определения PRG, когда его выходной сигнал отличается от однородного для небольших цепей . Эта идея восходит к Яо и на самом деле является самым сильным из возможных определений, которое вы можете попросить при явном стремлении к псевдослучайности для ограниченных в вычислительном отношении наблюдателей.

Второй аспект - это выбор параметров, в которых мы ограничиваем размер схемы равным а разность вероятностей принятия - 1 / n , где n также является выходным размером PRG. Этот выбор несколько отличается от обычного криптографического тот , где размер схемы является р о л у ( п ) и разность вероятности требуется , чтобы быть меньше , чем любой р ö л у ( п ) . В нашем случае конкретные параметры (а не p o l y ( n $n$$1/n$$n$$poly(n)$$poly(n)$$poly(n)$) были необходимы, чтобы получить максимально точные результаты, в том числе, в частности, полиномиальное моделирование. Хотя в принципе можно было иметь 3 разных параметра, оказалось, что наши результаты работали по существу одинаково, поэтому мы сложили их в один (в дополнение к входному размеру который рассматривался как функция н ).$l(n)$$n$

Я ни в коем случае не эксперт в этом, но ключевой компонент определения псевдослучайности (в отличие от попыток определить случайность) состоит в том, что цель чего-то «псевдослучайного» состоит в том, чтобы обмануть цепь. Другими словами, мотивация состоит в том, чтобы думать о псевдослучайной строке, подаваемой в схему вместо действительно случайной строки.

В этом смысле это не совсем то, что вы пытаетесь сделать вид, что и G ( y ) «выглядят одинаково». Это то, что они «выглядят одинаково» для схемы (обязательно ограниченной сложности).$x$$G(y)$

Таким образом, роль схемы имеет решающее значение, а не просто «тестовая функция».

Надеюсь, я смогу немного подробнее рассказать об ответе Суреша. Во- первых, я не думаю , что строгость неравенства необходимо в вашем , и я также не знаю , почему 1 / п требуется, а не 1 / +2 п или что - то другое. Однако практически я думаю, что 1 / n достаточно, чтобы получить некоторые интересные теоретические результаты.$(*)$$1/n$$1/2n$

Но тогда вы почти наверняка захотите утверждать, что каждый вычислим за некоторое время, скажем, экспоненциальный. Далее, я думаю, вам придется утверждать, что l ( n ) < n . Вы можете думать о l ( n ) как о длине семени. Таким образом, G i является псевдослучайным, если оно может увеличить количество битов в случайной строке длиной l ( n ), не будучи обнаруженным схемой размером меньше n .$G_i$$l(n) < n$$l(n)$$G_i$$l(n)$$n$