Determinista y la complejidad de la comunicación aleatorio de la igualdad conjunto

Question

Dos procesadores $ A, B $ con entradas $ a \ in \ {0, 1 \} ^ n $ (por $ A $) y $ b \ in \ {0, 1 \} ^ n $ (Por $ B $) quieren decidir si $ a = b $. $ A $ no sabe $ B $’s de entrada y viceversa.

A puede enviar un mensaje $ m (a) \ in \ {0, 1 \} ^ n $ que $ B $ puede utilizar para decidir $ a = b $. Las reglas de comunicación y de cálculo se denominan protocolo .

• Mostrar todos los protocolos que debe satisfacer determinista $ | m (a) | \ Ge $ n.
• Estado un protocolo aleatorio que utiliza sólo $ O (\ log_2n) $ Bits. El protocolo siempre debe aceptar si $ a = b $ y aceptar con probabilidad en más de $ 1 / n $ contrario. Demostrar su corrección.

Answer 1

En el primer punto, intente un argumento de recuento. ¿Cuántos mensajes diferentes $ m (a) puede $ $ B $ recibir, si $ | m (a) |

En el segundo punto, probar primero analizar el protocolo aleatorizado trivial (fijación al azar $ \ log (n) $ posiciones de la cadena y el envío de estos bits de $ a $). Claramente, este protocolo siempre acepta si $ a = b $. Supongamos $ a \ neq b $, ¿cuál es la probabilidad de que $ \ log (n) $ trozos recogidos al azar son los mismos? ¿Eso basta?