Сложение двух n-битных чисел схемой размера \(O(n)\) и глубины \(O(\log n)\). Умножение двух n-битных чисел схемой размера \(O(n^2)\) и глубины \(O(\log n)\).

Коммуникационные протоколы, комбинаторные прямоугольники. Коммуникационная сложность предиката равенства. Компромисс между временем и памятью для машины Тьюринга, решающей задачу о палиндроме.

Текущая версия конспекта.