Deterministische und randomisierte Kommunikationskomplexität der festgelegten Gleichheit

Question

Zwei Prozessoren $ A, B $ mit Inputs $ a in {0, 1 }^n $ (für $ a $) und $ B in {0, 1 }^n $ (für $ b $) Möchten Sie entscheiden, ob $ A = B $. $ A $ kennt $ b $ nicht und umgekehrt.

A kann eine Nachricht $ m (a) in {0, 1 }^n $ senden, mit der $ B $ $ A = B $ entscheiden kann. Die Kommunikations- und Berechnungsregeln werden als a genannt Protokoll.

• Zeigen Sie, dass jedes deterministische Protokoll $ | m (a) | erfüllen muss ge n $.
• Geben Sie ein randomisiertes Protokoll an, das nur $ O ( log_2n) $ Bits verwendet. Das Protokoll sollte immer akzeptieren, ob $ A = B $ mit Wahrscheinlichkeit höchstens 1 $/n $ akzeptiert. Beweisen seine Richtigkeit.

Answer 1

Versuchen Sie für den ersten Punkt ein Zählargument. Wie viele verschiedene Nachrichten $ m (a) $ kann $ b $ erhalten, wenn $ | m (a) |

Versuchen Sie für den zweiten Punkt zunächst das triviale randomisierte Protokoll ($ log (n) $ -Positionen der Zeichenfolge zufällig und senden Sie diese Teile von $ a $). Natürlich akzeptiert dieses Protokoll immer, ob $ A = B $. Angenommen, $ a neq b $, wie hoch ist die Wahrscheinlichkeit, dass $ log (n) $ zufällig ausgewählte Bits gleich sind? Reicht das aus?