Alice e Bob têm strings de n bits e querem descobrir se são iguais enquanto fazem pouca comunicação. A solução aleatória padrão é tratar as seqüências de n bits como polinômios de grau e depois avaliar os polinômios sobre alguns elementos escolhidos aleatoriamente em um campo de tamanho maior que . Isso requer comunicação .
Suponha, em vez disso, que fixemos uma ordem lexicográfica sobre as seqüências de caracteres e desejemos determinar qual sequência é "maior", o que equivale a encontrar o bit mais à esquerda onde as sequências diferem.
Existe um protocolo aleatório semelhante para fazer isso ou um limite inferior conhecido? Isso parece estar relacionado ao teste de positividade de polinômios.
ps Embora a ordem lexicográfica pareça a mais óbvia, eu estou bem com outras ordens: para o propósito em que estou interessado, tudo o que precisamos é de alguma ordem.
fonte
Respostas:
Isso é conhecido como problema maior que a complexidade da comunicação. Existe um algoritmo com complexidade de comunicação (Exercício 3.18 no livro Nisan-Kushilevitz).O ( logn )
Edit: O algoritmo é devido ao Nisan (página 10): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&rep=rep1&type=pdf
Ele usa a abordagem sugerida por @Sasho Nikolov abaixo --- executando uma pesquisa binária usando testes de igualdade com erro constante para fazer as comparações. Isso pode ser feito com consultas usando o "algoritmo de pesquisa binária barulhenta" de Feige, Peleg, Raghavan e Upfal: http://cs.brown.edu/~eli/papers/SICOMP23FRPU.pdfO ( logn )
Para obter um protocolo de aleatoriedade privado (não explícito), é possível aplicar o resultado de Newman: http://pdf.aminer.org/000/933/113/private_vs_common_random_bits_in_communication_complexity.pdf
fonte
Consulte A complexidade de comunicação da adição .
fonte