Deterministica e randomizzato complessità comunicazione dell'uguaglianza set

Question

Due processori $ A, B $ con ingressi $ a \ in \ {0, 1 \} ^ n $ (per $ A $) e $ b \ in \ {0, 1 \} ^ n $ (A $ B $) vogliono decidere se $ a = b $. $ A $ non conosce $ B $’s di ingresso e viceversa.

A può inviare un messaggio $ m (a) \ in \ {0, 1 \} ^ n $ che $ B $ può utilizzare per decidere $ a = b $. Le regole di comunicazione e di calcolo sono chiamati a protocollo .

• Mostra che ogni protocollo deterministico deve soddisfare $ | m (a) | \ Ge n $.
• Stato un protocollo randomizzato che utilizza solo $ O (\ log_2n) $ bit. Il protocollo dovrebbe sempre accettare se $ a = b $ e accettare con probabilità al massimo $ 1 / $ n altrimenti. Dimostrare la sua correttezza.

Answer 1

Per il primo punto, provare un argomento di conteggio. Quanti messaggi diversi $ m (a) $ può $ B $ riceverà, se $ | m (a) |

Per il secondo punto, provare prima l'analisi del protocollo randomizzato banale (in modo casuale fissaggio $ \ log (n) $ posizioni della stringa e l'invio di questi pezzi di $ A $). Chiaramente, questo protocollo accetta sempre se $ a = b $. Si supponga $ a \ neq b $, qual è la probabilità che $ \ log (n) $ bit raccolti in modo casuale sono la stessa cosa? Ritiene che basti?