设置平等的确定性和随机沟通复杂性

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/n $接受否则。证明其正确性。

Answer 1

对于第一点，请尝试计数参数。如果$ | m（a）|

对于第二点，请尝试首先分析琐碎的随机协议（随机固定字符串的$ log（n）$位置并发送$ a $的这些位）。显然，如果$ a = b $，此协议总是接受。假设$ a neq b $，$ log（n）$随机选择的位相同的概率是多少？足够吗？