Tenho um problema bastante único para resolver e espero que alguém aqui possa me dar algumas dicas sobre a melhor forma de enfrentá-lo.
Problema: Suponha que uma lista de N números seja compartilhada entre um conjunto de participantes de tal maneira que nenhum participante realmente conheça algum dos números que compartilha. Todos os participantes conhecem N (o tamanho da lista de números) e a soma de todos os números da lista, mas nada mais a priori.
Trabalhando juntos, é possível comparar dois números compartilhados aeb de tal maneira que os participantes aprendam se a afirmação "a <b" é verdadeira, mas nada mais. No entanto, isso é extremamente caro (leia-se: pode levar muitos segundos, talvez até minutos, para concluir uma única comparação). Veja o final deste post para obter mais informações sobre como isso é possível.
No final do dia, as partes desejam exibir quais índices na lista correspondem ao "percentual K superior" (o K% que é o maior) números compartilhados na lista. Obviamente, isso pode ser feito classificando ou usando um algoritmo de seleção "top K". No entanto, eles tendem a usar muitas comparações, o que deve ser evitado. (Estes são O (n log n) ou O (n), com constantes ocultas razoavelmente grandes.)
Outra alternativa é "adivinhar" um número X para o qual (1-K)% são menores que X e K% são maiores. Em seguida, você pode comparar cada elemento com X e ver quantos são maiores e quantos são menores. Se seu palpite estava errado, revise-o usando algo como uma pesquisa binária até convergir para uma solução correta. Isso leva muito menos comparações se o seu palpite for bom.
Então, minha pergunta é:
Dado apenas N e a soma, qual é a melhor maneira de "prever" X?
Obviamente, isso dependerá da distribuição subjacente. Para diferentes casos de uso, a distribuição subjacente provavelmente será diferente, mas será conhecida, por isso estou interessado em boas soluções para todas as comuns (normal, uniforme, exponencial, talvez algumas outras). Eu também adoraria ouvir sugestões sobre a melhor forma de fazer a pesquisa "binária" para minimizar o número de etapas, considerando-se a distribuição subjacente.
APÊNDICE: Cada valor da lista é compartilhado entre os participantes usando o esquema de compartilhamento secreto de Shamir. Suponha que haja M participantes e a lista tenha comprimento N. Então, o i-ésimo número da lista é representado por um polinômio de grau M-1 sobre algum campo finito F. O termo constante de é o número que é compartilhados, todos os outros coeficientes são escolhidos uniformemente aleatoriamente a partir de F. As ações do j-ésimo participante são então ,f i f i ( j ) 1 ≤ i ≤ N. Dada essa participação, o participante não possui informações (no sentido teórico da informação) sobre o número; de fato, nenhum subconjunto apropriado de participantes pode combinar conhecimento para obter informações sobre os números compartilhados. No entanto, usando uma técnica sofisticada de computação segura com várias partes, é possível determinar se um valor compartilhado é menor que outro sem revelar mais informações. Essa técnica envolve a cooperação de todos os participantes, razão pela qual é tão dispendiosa e deve ser realizada o menor número de vezes possível.
Respostas:
Você parece fazer duas perguntas relacionadas:
Estes podem precisar de números muito diferentes de comparações aos pares.
Outro aspecto que pode ter um impacto significativo é o que as informações são compartilhadas. Todo mundo sabe o número que recebeu, sabe a soma e os resultados sim / não das comparações em que participaram. No entanto, você também diz que “as partes desejam exibir quais índices na lista correspondem ao topo”, portanto, você sugere que algumas informações sobre os índices serão compartilhadas. Dependendo do que exatamente é compartilhado, você poderá obter soluções muito diferentes novamente.
fonte