Коммуникационная сложность: различия между версиями

Нижняя оценка для EQ
Метки: правка с мобильного устройства правка из мобильной версии
(Нижняя оценка для EQ)
Метка: редактор вики-текста 2017
|}
 
Как мы видим, функция <math>EQ</math> равна 1 только в ячейках, где {{mvar|x}} равно {{mvar|y}} (т.е., на диагонали).
 
=== Теорема: <math>D(EQ) = n</math> ===
 
Доказательство. Предположим, что <math>D(EQ) \leq n-1</math>, то есть существует протокол, который решает задачу проверки равенства для всех пар битовых строк длины {{mvar|n}}, передавая при этом не более <math>n-1</math> бита. Давайте для каждой возможной пары одинаковых строк <math>(x, x)</math> (для них <math>EQ(x, x)=1</math>) выпишем в строчку все биты, которые пересылались в протоколе. Всего таких различных пар <math>(x,x)</math> ровно <math>2^n</math>, а различных битовых строк длины не более <math>n-1</math> всего <math>2 + 4 + \dotsb + 2^{n-1} = 2^n - 2 < 2^n</math>. По [[Принцип Дирихле (комбинаторика)|принципу Дирихле]] найдутся две пары <math>(x, x)</math> и <math>(x', x')</math>, для которых получились одинаковые строки, то есть в протоколе пересылались одни и те же биты. Так как множество пар строк, для которых пересылались одинаковые биты, задаёт прямоугольник, то <math>EQ(x, x')</math> и <math>EQ(x', x)</math> тоже должны быть равны 1, что противоречит тому, что <math>x \neq x'</math>. Следовательно наше предположение неверно, а значит <math>D(EQ) > n-1</math>
 
Другими словами, если <math>D(EQ)</math> меньше {{mvar|n}}, то мы должны уметь покрыть все единички матрицы EQ при помощи менее <math>2^n</math> одноцветных прямоугольников (все ячейки которых помечены единицами). Однако, в матрице EQ ровно <math>2^n</math> единичек, и никакие две не могут лежать в одном одноцветном прямоугольнике, т.к. тогда в этот прямоугольник неизбежно попадую ячейки помеченные нулями. Поэтому, такого покрытия не существует, а значит <math>D(EQ)</math> как минимум {{mvar|n}}.
 
 
== Примечания ==