Детерминированная и рандомизированная сложность коммуникации установленного равенства

Question

Два процессора $ a, b $ с входами $ a in {0, 1 }^n $ (для $ a $) и $ b in {0, 1 }^n $ (для $ b $) хочу решить, $ a = b $. $ A $ не знает вклада $ b $ и наоборот.

A может отправить сообщение $ m (a) in {0, 1 }^n $, который $ b $ может использовать для определения $ a = b $. Правила связи и вычислений называются протокол.

• Покажите, что каждый детерминированный протокол должен удовлетворить $ | m (a) | ge n $.
• Укажите рандомизированный протокол, который использует только $ o ( log_2n) $ биты. Протокол всегда должен принять, если $ a = b $ и принять с вероятностью не более 1 долл. США/н. Докажите его правильность.

Answer 1

Для первого пункта попробуйте считать аргумент. Сколько разных сообщений $ m (a) $ может получить $ b $, если $ | m (a) |

Во втором пункте попробуйте сначала проанализировать тривиальный рандомизированный протокол (случайным образом исправлять $ log (n) $ позиции строки и отправить эти биты $ a $). Ясно, что этот протокол всегда принимает, если $ a = b $. Предположим, что $ a neq b $, какова вероятность того, что $ log (n) $ случайно выбранные биты одинаковы? Этого достаточно?