Покрытия нулей и единиц матрицы \(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)\).