Формальное определение детерминированных и вероятностных коммуникационных протоколов. Дерево протокола. Прямоугольники, соответствующие листьям дерева протокола.

Матрица функции, ее разбиение на одноцветные прямоугльники, неравенство $\log C^R(f) < D(f)$.

Методы оценки $C^R(f)$: (1) трудные множества и размеры одноцветных прямоугольников и (2) ранг матрицы.

Нижние оценки детерминированной сложности предикатов EQ, GT, DISJ, IP этими методами.