А. Тимофеев

Монотонные схемы: односторонние функции и псевдослучайные генераторы

На докладе будет разобрана одноименная статья Oded Goldreich и Rani Izrak.
(в свободном доступе: http://www.wisdom.weizmann.ac.il/~oded/PDF/mono-cry.pdf)

Основными результатами являются:

• существование односторонней функции, вычислимой полимиальной монотонной схемой,
• псевдослучайные генераторы не являются монотонными функциями.

(Оба результата сформулированы при условии существования данных объектов.)

Напомним, что при выполнении некоторых утверждений данные объекты могут быть вычислены схемами из NC⁰. Что оказывается неверно для класса монотонных схем.