Невозможность избавиться от \( \log n \) в последнем утверждении (функция \( EQ \)). Для случайной функции метод размера прямоугольников значительно лучше метода трудного множества. Функция \( DISJ_k \) для \( k= \log n \). Верхние оценки \( \log C^0(DISJ_k)=O(\log n) \), \( \log C^1(DISJ_k)=O(\log n) \). Нижняя оценка \( D(DISJ_k)=\Omega(\log^2 n) \).