Покрытия нулей и единиц матрицы $M(f)$ предиката $f$. Применение метода размера прямоугольников для оценки этого покрытия. Недетерминированная сложность предикатов. Неравенство $D(f) < 2^{N(f)}+1$. Пример предиката (EQ) с экспоненциальным разрывом между $N(f)$ и $D(f)$.

Неравенство $D(f) < (N(f)+2)(N(\lnot f)+1)$.

Пример ($DISJ_{nk}$) функции с квадратичным разрывом между $D(f)$ и $N(f),N(\lnot f)$.