Algoritmos aleatórios eficientes e simples, onde o determinismo é difícil

Costumo ouvir que, para muitos problemas, conhecemos algoritmos aleatórios muito elegantes, mas não, ou apenas soluções determinísticas mais complicadas. No entanto, só conheço alguns exemplos para isso. Mais proeminentemente

• Quicksort randomizado (e algoritmos geométricos relacionados, por exemplo, para cascos convexos)
• Randomizado Mincut
• Teste de identidade polinomial
• Problema de Klee's Measure

Entre estes, apenas o teste de identidade polinomial parece ser realmente difícil sem o uso de aleatoriedade.

Você conhece mais exemplos de problemas em que uma solução aleatória é muito elegante ou muito eficiente, mas soluções determinísticas não são? Idealmente, os problemas devem ser fáceis de motivar para leigos (ao contrário de, por exemplo, teste de identidade polinomial).

Classificação de porcas e parafusos

O problema a seguir foi sugerido por Rawlins em 1992: Suponha que você receba uma coleção de n porcas e parafusos. Cada parafuso se encaixa exatamente em uma porca e, caso contrário, as porcas e os parafusos têm tamanhos distintos. Os tamanhos são muito próximos para permitir a comparação direta entre pares de parafusos ou pares de porcas. No entanto, você pode comparar qualquer porca com qualquer parafuso, tentando parafusá-las; em tempo constante, você descobrirá se o parafuso é muito grande, pequeno ou adequado para a porca. Sua tarefa é descobrir qual parafuso se encaixa em cada porca, ou equivalente, para classificar as porcas e parafusos por tamanho.

Uma variante direta do quicksort aleatório resolve o problema em tempo com alta probabilidade. Escolha um parafuso aleatório; use-o para particionar as nozes; use a porca correspondente para particionar os parafusos; e recursar. No entanto, encontrar um algoritmo determinístico que seja executado em não é trivial. Os algoritmos determinísticos de tempo foram finalmente encontrados em 1995 por Bradford e independentemente por Komlós, Ma e Szemerédi. Sob o capô, os dois algoritmos usam variantes da rede de classificação paralela AKS, de modo que a constante oculta no limite de tempo é bastante grande; a constante oculta para o algoritmo aleatório é 4.o ( n 2 ) O ( n log n ) O ( n log n $O(n \log n)$$o(n^2)$$O(n\log n)$$O(n\log n)$

• Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Noar e Rafail Ostrovsky. Porcas e parafusos correspondentes. Proc. 5th Ann. ACM-SIAM Symp. Algoritmos Discretos , 690-696, 1994.
• Noga Alon, Phillip G. Bradford e Rudolf Fleischer. Porcas e parafusos correspondentes mais rapidamente. Informar. Proc. Lett. 59 (3): 123-127, 1996.
• Phillip G. Bradford. Porcas e parafusos correspondentes da melhor maneira. Tech. Rep. MPI-I-95-1-025, Instituto Max Planck for Informatik, 1995. http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-025
• Phillip G. Bradford e Rudolf Fleischer. Porcas e parafusos correspondentes mais rapidamente. Proc. 6o. Int. Symp. Algoritmos de Computação. 402-408, 1995. Notas de aula Comput. Sci. 1004
• János Komlós, Yuan Ma e Endre Szemerédi. Porcas e parafusos correspondentes no tempo . SIAM J. Matemática Discreta. 11 (3): 347-372, 1998.$O(n\log n)$
• Gregory J. E. Rawlins. Comparado com o que? : Uma Introdução à Análise de Algoritmos . Computer Science Press / WH Freeman, 1992.

Uma vez que você não está apenas falando sobre o poli-tempo, mas analisando os vários modelos de computação que estudamos, há exemplos em todos os lugares:

No espaço de log: conectividade ST não direcionada (em RL desde 1979 e em L somente desde 2005)

No NC: como encontrar uma correspondência perfeita em um gráfico bipartido em paralelo (no RNC e ainda não se sabe que ele está no NC)

Nas provas interativas: as determinísticas dão NP, enquanto as aleatórias podem fazer o PSPACE. Relacionado: verificar uma prova deterministicamente requer a verificação de todas as provas, enquanto as provas PCP permitem verificar apenas um número constante de bits.

No Projeto de Mecanismos Algorítmicos: muitos mecanismos de aproximação verdadeiros randomizados, sem contrapartida determinística.

Na complexidade da comunicação: a função de igualdade requer comunicação linear determinística, mas logarítmica (ou, dependendo do modelo exato, constante) comunicação aleatoriamente.

Em árvores de decisão: avaliar uma árvore e-ou requer consultas lineares deterministicamente, mas muito menos com randomização. Isso é essencialmente equivalente à poda alfa-beta, que fornece um algoritmo sub-linear aleatório para avaliação da árvore de jogo.

Nos modelos de streaming, modelos de computação distribuída: veja respostas anteriores.

A maioria dos algoritmos de streaming

No modelo de computação de streaming ( AMS , livro ), um algoritmo processa uma sequência on-line de atualizações e é restrito a manter apenas o espaço sublinear. A qualquer momento, o algoritmo deve ser capaz de responder a uma consulta.

Para muitos problemas, existem algoritmos de fluxo aleatório no espaço sublinear, enquanto comprovadamente nenhum algoritmo determinístico pode resolver o problema no espaço sublinear. Isso está relacionado a lacunas entre a complexidade da comunicação aleatória e determinística. Um exemplo simples é o problema de contagem distinta : a cada etapa o algoritmo recebe um número inteiro e deve ser capaz de aproximar, ou seja, o número de números inteiros distintos vistos até o passo . É relativamente fácil mostrar que qualquer algoritmo determinístico que atinge uma aproximação constante deve usar o espaço (consulte, por exemplo, notas de aulai t ∈ [ n ] D m = | { i t : t = 1 … m } | m Ω ( n ) O ( log n ) O ( $t$$i_t \in [n]$$D_m = |\{i_t: t = 1\ldots m\}|$$m$$\Omega(n)$de Piotr Indyk). Por outro lado, o algoritmo de amostragem inteligente de Flajolet e Martin (análise simples com aleatoriedade limitada no artigo AMS acima) consegue uma aproximação constante em bits. O trabalho mais recente sobre o problema fornece um algoritmo ideal que calcula uma aproximação de .$O(\log n)$1±$O(\frac{1}{\epsilon^2} + \log n)$$1\pm \epsilon$

Localizando um conjunto independente máximo em uma rede distribuída de nós com o grau máximo . Existe um limite inferior conhecido [3] de que vale para algoritmos aleatórios e determinísticos.Δ $n$$\Delta$$\min(\Omega(\log\Delta),\Omega(\sqrt{\log n}))$

A seguir, é apresentado um algoritmo distribuído aleatório simples [1], que prossegue em rodadas síncronas . (Em uma rodada, cada nó pode executar alguma computação local e enviar mensagens para seus vizinhos. Essas mensagens são garantidas para serem recebidas antes do início da próxima rodada.)$u$

1. Em cada rodada, cada nó ativo marca-se com probabilidade onde é o grau de ; se , simplesmente entra no conjunto independente. (Inicialmente, todos os nós estão ativos.)$u$$1/d_u$$d_u>0$$u$$d_u=0$$u$
2. Se é o único nó marcado em sua vizinhança, entra no conjunto independente, se desativa e notifica todos os seus vizinhos para se desativarem. Os graus dos nós ativos restantes são diminuídos de acordo, ou seja, todas as arestas dos nós desativados são removidas.$u$$u$
3. Caso contrário, se houver algum nó vizinho que também esteja marcado, o vértice de grau inferior se desmarca e permanece ativo.$v$

Pode-se mostrar que esse algoritmo termina em rodadas com alta probabilidade, argumentando que metade das arestas restantes são excluídas a cada rodada. Por outro lado, o algoritmo distribuído determinístico mais rápido conhecido [2] leva rodadas e é consideravelmente mais complicado.$O(\log n)$$O(n^{1/\sqrt{\log n}})$

[1] Michael Luby: um algoritmo paralelo simples para o problema do conjunto independente máximo. SIAM J. Comput. 15 (4): 1036-1053 (1986) http://dx.doi.org/10.1137/0215074

[2] Alessandro Panconesi, Aravind Srinivasan: Sobre a complexidade da decomposição de rede distribuída. J. Algorithms 20 (2): 356-374 (1996) http://dx.doi.org/10.1006/jagm.1996.0017

[3] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: computação local: limites inferiores e superiores. CRR abs / 1011.5470 (2010) http://arxiv.org/abs/1011.5470

Eleição do líder em um círculo anônimo de processos

Suponha que você tenha uma rede em anel de processos que não possuem IDs e que se comunicam através da passagem de mensagens. Inicialmente, todo processo está no mesmo estado. Você deseja projetar um algoritmo distribuído de forma que, eventualmente, exatamente processo entre no estado eleito e todos os outros processos entrem no estado não eleito . Esse é o chamado problema de eleição de líderes, que é uma das tarefas fundamentais de quebra de simetria em um sistema distribuído e tem muitas aplicações.$1$

Há um argumento simples (por exemplo, [1]) de que não há algoritmo determinístico de eleição de líder para um anel anônimo.

Modelo: Assumimos que o cálculo avança em rodadas síncronas em que, em cada rodada, todo processo realiza alguma computação local, envia mensagens para seus vizinhos no ringue e recebe mensagens de seus vizinhos.

Por uma questão de uma contradição, vamos supor que existe tal um líder determinista algoritmo de eleição . É suficiente mostrar que, no início de qualquer rodada , todos os processos estão no mesmo estado, pois isso implica que não pode haver exatamente processo no estado eleito . Como os processos não têm IDs e a rede é simétrica, todo processo está no mesmo estado inicial, o que fornece a base de indução.$A$$r\ge 0$$1$

Para a etapa de indução, considere alguns e suponha que todo processo esteja no mesmo estado no início do . Portanto, como o algoritmo é determinístico, todo processo executa exatamente a mesma computação e envia exatamente as mesmas mensagens durante a rodada . Por sua vez, isso implica que todo processo recebe exatamente as mesmas mensagens durante , no início da rodada , está no mesmo estado. Assim, nenhum algoritmo pode existir.$r\ge 0$$r$$A$$r$$r$$r+1$$A$

Se é um algoritmo aleatório, por outro lado, e os processos sabem o tamanho do anel , existe uma maneira fácil de quebrar a simetria, gerando um ID aleatório do intervalo , o que resultará em IDs únicos. para todos os processos com alta probabilidade. Um algoritmo simples e ingênuo prossegue, permitindo que cada processo envie seu ID ao longo do anel e instrua os processos a encaminhar apenas mensagens contendo o maior ID visto até agora. Isso garante que apenas o processo que gerou o maior ID receberá sua própria mensagem depois de percorrer todo o anel e se eleger como líder.$A$$n$$[1,n^4]$

[1] Dana Angluin: propriedades locais e globais em redes de processadores (Resumo estendido). STOC 1980: 82-93. http://doi.acm.org/10.1145/800141.804655

Problema majoritário em um modelo de consulta.

Problema . Recebemos um conjunto de bolas coloridas com duas ou mais cores. O objetivo é encontrar uma bola da cor majoritária (ou seja, uma cor que ocorra mais de duas vezes) assumindo que essa cor existe, usando consultas no formato "A bola e a bola têm a mesma cor?". A estratégia deve estar inconsciente, ou seja, as consultas não podem depender dos resultados das consultas anteriores.$n$$i$$j$

Algoritmo Aleatório . Escolha uma bola aleatória e verifique se mais de bolas têm a mesma cor. Esse algoritmo é executado em tempo em expectativa.$n/2$$O(n)$

algoritmo determinístico$O(n)$ não é trivial e é uma boa aplicação de expansores.

FRK Chung, RL Graham, J. Mao e AC Yao, estratégias inconscientes e adaptativas para os problemas da maioria e da pluralidade, Proc. COCOON 2005 , pp. 329–338.