Связь между детерминированной сложностью и разбиениями матрицы функции на одноцветные прямоугольники: \( \log C^P(f) \) не превосходит \( D(f) \) и, обратно, \( D(f)=O(\log C^P(f)) \). Теорема о связи детерминированной и недетерминированной сложности: \( D(f) \) есть \( O(\log C^0(f) \log C^1(f)) \). Универсальность метода размера прямоугольников для оценки \( \log C^0(f) \) с точностью до \( \log n \): для всех \( f \) найдется распределение вероятностей \( \mu \) на нулях функции, для которого \( \log C^0(f) \) меньше \( -\log \mu(R)+ \log n \) для всех нуль-цветных прямоугольников \( R \).