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

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

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

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