Построение генераторов псевдослучайных чисел

Генератором псевдослучайных чисел (ПСЧ) называется полиномиально вычислимая функция G, отображающая слова какой-то длины n в слова длины n со следующим свойством. Любой полиномиально вычислимый тест не может отличить случайную величину G(x) (где x имеет равномерное распределение на словах длины n) от случайной величины, равномерно распределенной среди всех слов длины m. Нетрудно доказать, что если P=NP, то генераторов ПСЧ не существует. Поэтому для доказательства существования генератора ПСЧ нужна гипотеза о различии классов P и NP или более сильная гипотеза. В спецкурсе будет рассказано о конструкции Хостада — Импальяццо — Левина — Люби генератора ПСЧ, исходя из любой односторонней функции. Кроме того, будет рассказано о конструкции Нисана — Вигдерсона генератора ПСЧ, исходя из функции с большой схемной сложностью.

Необходимы предварительные знания: начала сложности вычислений (машины Тьюринга, схемы из функциональных элементов, взаимоотношения между ними, вероятностные алгоритмы, классы P, BPP, NP), односторонние функции.