Случайная монотонная функция

В статье Разборова-Рудича « Естественные доказательства» , стр. 6, в той части, в которой они обсуждают, что есть «сильные доказательства нижних границ против моделей монотонных схем» и как они вписываются в картину, есть следующие предложения:

Здесь проблема не в конструктивности - все свойства, используемые в этих доказательствах, возможны - но в том, что нет хорошего формального аналога условия больших размеров. В частности, никто не сформулировал работоспособное определение «случайной монотонной функции».

Разве не легко отличить выходные данные монотонной функции от случайной строки? Разве существование сильных нижних границ не говорит нам, что таких вещей нет?

Мой вопрос:

Что они подразумевают под работоспособным определением «случайной монотонной функции» ?

Я не уверен, но я думаю, что проблема здесь в том, что у нас нет строгих предположений относительно генераторов псевдослучайных монотонных функций (по крайней мере, ни одного из известных мне). Идея доказательства в статье Разборова-Рудича заключается в следующем:

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

Если бы мы переформулировали теорему в терминах монотонных функций и монотонных схем, мы бы хотели сказать,

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

но теперь доказательство из статьи перестает работать, потому что наш псевдослучайный генератор выводит общие функции, не обязательно монотонные, и мы не можем использовать наше естественное свойство, чтобы нарушить его, потому что даже относительно большое подмножество монотонных функций не будет большим по сравнению с общие функции, для самого набора монотонных функций не так много относительно набора всех функций ( http://en.wikipedia.org/wiki/Dedekind_number ). Мы могли бы определить какой-нибудь генератор псевдослучайных монотонных функций и использовать естественное свойство для его разрыва, но у нас, вероятно, не было бы эквивалентности между этим генератором и односторонними функциями, поэтому теорема не была бы такой интересной.

Может быть, эта трудность может быть исправлена ​​(но я не думаю, что это следует непосредственно из доказательства в статье), и, возможно, проблема с монотонными функциями лежит где-то еще. Мне бы очень хотелось, чтобы кто-то более опытный, чем я, подтвердил мой ответ или показал, где я ошибаюсь.