Коммуникационная сложность (2017). Лекция 5

Покрытия нулей и единиц матрицы M(f) предиката f. Применение метода размера прямоугольников для оценки этого покрытия. Недетерминированная сложность предикатов. Неравенство D(f)<2^N(f)+1. Пример предиката (EQ) с экспоненциальным разрывом между N(f) и D(f).

Неравенство D(f)<(N(f)+2)(N(¬f)+1).

Пример (DISJ_nk) функции с квадратичным разрывом между D(f) и N(f),N(¬f).

Страница лекции на CSClub