Quando a randomização acelera os algoritmos e "não deveria"?

39

Prova de Adleman que está contido em P / p o l y mostra que, se houver um algoritmo aleatório para um problema que é executado no tempo t ( n ) em entradas de tamanho n , em seguida, há também um algoritmo determinística para o problema que é executado no tempo Θ ( t ( n ) n ) em entradas de tamanho n [o algoritmo executa o algoritmo aleatório em Θ ( n )BPPP/polyt(n)nΘ(t(n)n)nΘ(n)seqüências de aleatoriedade independentes. Deve haver aleatoriedade para o algoritmo repetido que seja bom para todos os 2n entradas possíveis]. O algoritmo determinístico não é uniforme - pode se comportar de maneira diferente para diferentes tamanhos de entrada. Portanto, o argumento de Adleman mostra que - se alguém não se importa com a uniformidade - a randomização pode acelerar os algoritmos apenas por um fator linear no tamanho da entrada.

Quais são alguns exemplos concretos em que a randomização acelera a computação (tanto quanto sabemos)?

Um exemplo é o teste de identidade polinomial. Aqui, a entrada é um circuito aritmético de tamanho n que calcula um polinômio m-variado sobre um campo, e a tarefa é descobrir se o polinômio é identicamente zero. Um algoritmo aleatório pode avaliar o polinômio em um ponto aleatório, enquanto o melhor algoritmo determinístico que conhecemos (e possivelmente o melhor que existe) avalia o polinômio em muitos pontos.

Outro exemplo é a árvore de abrangência mínima, onde o melhor algoritmo aleatório de Karger-Klein-Tarjan é o tempo linear (e a probabilidade de erro é exponencialmente pequena!), Enquanto o melhor algoritmo determinístico de Chazelle é executado no tempo ( α é a função inversa de Ackermann, portanto a aceleração da randomização é realmente pequena). Curiosamente, foi provado por Pettie e Ramachandran que, se existe um algoritmo de tempo linear determinístico não uniforme para uma árvore de abrangência mínima, também existe um algoritmo de tempo linear determinístico uniforme.O(mα(m,n))α

Quais são alguns outros exemplos? Quais exemplos você sabe onde a aceleração da randomização é grande, mas isso é possivelmente porque ainda não encontramos algoritmos determinísticos suficientemente eficientes?

Dana Moshkovitz
fonte
5
Intimamente relacionado: Problemas no BPP não conhecidos por P
usul
Você sempre pode converter qualquer algoritmo aleatório em um algoritmo determinístico, substituindo o gerador aleatório por um gerador pseudo-aleatório de qualidade criptográfica. Sob suposições criptográficas plausíveis de que, até onde sabemos, são válidas, isso funciona bem. Portanto, minha resposta seria: "até onde sabemos, a resposta é: não existem problemas do mundo real". (Em outras palavras, com o melhor de nosso conhecimento, a diferença no tempo de execução reflete nossa incapacidade de provar limites de tempo de execução apertado, em vez de qualquer diferença subjacente real.)
DW
1
Sob premissas razoáveis ​​de dureza, você pode alimentar a aleatoriedade do algoritmo a partir de um gerador pseudo-aleatório; no entanto, para obter um algoritmo determinístico disso, é necessário executar o algoritmo em todas as sementes possíveis. Isso aumenta o tempo de execução!
Dana Moshkovitz
Além do argumento de Dana, acho que, para des randomizar o BPP, o PRG precisa ser executado em mais tempo que o algoritmo original (embora eu não saiba qual deve ser a diferença). Além disso, isso pode ilustrar uma lacuna (fundamental?) Entre certeza e confiança exponencialmente alta: basta repetir um algoritmo aleatório vezes (para qualquer constante c ) para obter a probabilidade de correção 2 - O ( c ) , mas a versão determinística precisa para verificar todas as sementes polinomialmente. cc2O(c)
usul
@DanaMoshkovitz, depende se você aborda isso de uma perspectiva teórica ou do profissional. Do ponto de vista do profissional, não, você não precisa fazer isso. Veja a construção que descrevi em cs.stackexchange.com/a/41723/755 , que executa o algoritmo em apenas sementes. Sob o modelo de oráculo aleatório, pode-se mostrar que não há aumento no tempo de execução assintótico e que nenhum adversário limitado computacionalmente poderá encontrar alguma entrada para o algoritmo em que o algoritmo produz a resposta errada. Provavelmente isso é bom o suficiente para todos os fins práticos. O(1)
DW

Respostas:

28

Eu não sei se randomização “deve” ou “não deve” ajudar, no entanto, teste de primalidade inteiro pode ser feito em tempo usando randomizados Miller-Rabin, enquanto que, tanto quanto eu sei, o mais conhecido algoritmos são deterministas ~ S ( N 4 ) assumindo GRH (determinista Miller-Rabin) ou ~ S ( n 6 ) incondicionalmente (variantes de AKS).O~(n2)O~(n4)O~(n6)

Emil Jeřábek apoia Monica
fonte
Embora haja razões para acreditar que a menor testemunha de composição para é do log de pedidos N log log N , o que daria um algoritmo ˜ O ( n 3 ) . Mas isso permanece não comprovado, mesmo sob conjecturas teóricas padrão de números, como variantes da UR. NlogNloglogNO~(n3)
Emil Jeřábek apoia Monica
Um problema semelhante é o teste de irredutibilidade polinomial em campos finitos, onde o algoritmo determinístico conhecido novamente tem limites piores que os algoritmos aleatórios, mas não me lembro dos detalhes.
Emil Jeřábek apoia Monica
19

Um exemplo antigo é a computação de volume. Dado um polítopo descrito por um oráculo de associação, existe um algoritmo aleatório em execução no tempo polinomial para estimar seu volume em um fator de , mas nenhum algoritmo determinístico pode se aproximar incondicionalmente .1+ϵ

O primeiro exemplo dessa estratégia aleatória foi de Dyer, Frieze e Kannan, e o resultado da dureza para algoritmos determinísticos é de Bárány e Füredi. Alistair Sinclair tem boas notas de aula sobre isso .

Não sei se entendi completamente a parte "e não deveria" da pergunta, então não tenho certeza se isso se encaixa na conta.

Suresh Venkat
fonte
1
[n/logn]n
9

Eu não sei se isso responde à sua pergunta (ou pelo menos parte dela). Mas para exemplos do mundo real, onde a randomização pode fornecer uma aceleração, está nos problemas de otimização e na relação com o teorema Sem almoço livre ( NFL ) .

Existe um artigo "Talvez não seja um almoço grátis, mas pelo menos um aperitivo grátis", onde é demonstrado que o emprego de algoritmos de randomização (otimização) pode ter melhor desempenho.

Abstrato:

f:XYXYsão conjuntos finitos. Esse resultado é chamado de [o] Teorema Sem Almoço Gratuito. Aqui são apresentados diferentes cenários de otimização. Argumenta-se por que o cenário no qual o Teorema do Almoço Gratuito não se baseia não modela a otimização da vida real. Para cenários mais realistas, argumenta-se por que as técnicas de otimização diferem em sua eficiência. Para um pequeno exemplo, essa afirmação é comprovada.

Referências:

  1. Sem Teoremas de Almoço Gratuito para Otimização ( teorema da NFL original para otimização)
  2. Talvez não seja um almoço grátis, mas pelo menos um aperitivo grátis
  3. FF
  4. Em classes de funções para as quais não há resultados de almoço grátis (é comprovado que a fração de subconjuntos que são copinhos é insignificantemente pequena)
  5. Duas classes amplas de funções para as quais um resultado sem almoço grátis não é válido (mostra que um resultado da NFL não se aplica a um conjunto de funções quando a duração da descrição das funções é suficientemente limitada)
  6. Almoços contínuos são gratuitos, além do design de algoritmos de otimização ótimos (mostra que, para domínios contínuos, a [versão oficial da] NFL não se sustenta. Esse teorema do almoço grátis é baseado na formalização do conceito de funções aleatórias de aptidão por meio de campos aleatórios )
  7. Além do almoço grátis: algoritmos realísticos para classes de problemas arbitrários (mostra que "todas as violações dos teoremas do almoço grátis podem ser expressas como distribuições não uniformes em bloco sobre subconjuntos de problemas que são copos ")
  8. Algoritmos meta-heurísticos baseados em enxame e teoremas de almoço sem almoço ("[..t], portanto, resultados para iterações ordenadas por tempo que não revisitam podem não ser verdadeiros para os casos de revisitar casos, porque as iterações revisitam uma suposição importante de copo necessário para provar os teoremas da NFL (Marshall e Hinton, 2010) ")
  9. Sem almoço grátis e aleatoriedade algorítmica
  10. Não há almoço grátis e benchmarks (uma abordagem da teoria dos conjuntos é generalizada para critérios não específicos para o copo , mas ainda observa que algoritmos aleatórios (não triviais) podem superar os algoritmos determinísticos em média ", [...] foi demonstrado que a probabilidade é inadequada para afirmar os resultados irrestritos da NFL no caso geral. [..] este artigo abandona a probabilidade, preferindo um arcabouço teórico-conjunto que evita limitações teóricas da medida, dispensando completamente a probabilidade ")

Resumo sobre almoços sem graça (e almoços grátis) por David H. Wolpert, Quanto custa o jantar? ( observe que os teoremas do tipo NFL nunca especificam um " preço " real devido ao seu tipo de prova)

Especificamente para otimização generalizada (GO):

  1. XZXZ

  2. f:XZ

  3. mf

    dm={dm(1),dm(2),...,dm(m)}
    t
    dm(t)={dmX(t),dmZ(t)}
    dmZ(t)f[dmX(t)]
  4. a={dtdmX(t):t=0..m}

  5. C(f,dm)

  6. C(.,.)

CfCfC(f,dm)f=f

Finalmente, uma observação simples (e não tão simples) por que a randomização (de uma forma ou de outra) pode fornecer desempenho superior em relação a algoritmos estritamente determinísticos.

  1. No contexto da otimização (embora não restrito a isso), um procedimento de pesquisa aleatória pode, em média, escapar local-extremo melhor do que a pesquisa determinística e atingir os extremos globais.
  2. 2AAAAA
Nikos M.
fonte
1

O melhor exemplo é a área atualmente considerada como melhor candidata a OWFs, onde parece que todo OWF popular que é preparado surpreendentemente possui um algoritmo subexponencial aleatório, enquanto não existe algoritmo subexponencial determinístico (por exemplo, fatoração inteira). De fato, em muitos casos, provavelmente existe um algoritmo eficiente, com algumas orientações (criptoanálise).

T ....
fonte
-5

Se você tiver um algoritmo usando randomização, sempre poderá substituí-lo por um algoritmo determinístico usando números pseudo-aleatórios: Faça a descrição do problema, calcule um código de hash, use esse código de hash como a semente de um bom gerador de números pseudo-aleatórios . Na prática, é isso que provavelmente acontece quando alguém implementa um algoritmo usando a randomização.

Se deixarmos de fora o código hash, a diferença entre esse algoritmo e um algoritmo usando a aleatorização verdadeira é que eu posso prever a sequência de números aleatórios gerados e eu poderia produzir um problema de modo que o número aleatório previsto aplicado ao meu problema sempre tome a pior decisão possível. Por exemplo, para o Quicksort com um pivô pseudo-aleatório, eu poderia construir uma matriz de entrada na qual o pivô pseudo-aleatório sempre encontrará o maior valor possível na matriz. Com verdadeira aleatoriedade, isso não é possível.

Com o código hash, seria muito difícil para mim construir um problema em que os números pseudo-aleatórios produzem piores resultados. Ainda posso prever os números aleatórios, mas se eu mudar o problema, a sequência de números pseudo-aleatórios muda completamente. Ainda assim, seria quase impossível para você provar que não consigo construir esse problema.

gnasher729
fonte
Eu sou novo em cstheory.SE. Então, downvoters - o que há de errado com esta resposta?
galdre
3
Duas coisas estão erradas: (1) não sabemos como construir números pseudo-aleatórios em geral, (2) mesmo quando sabemos como construí-los, eles são computacionalmente caros. Não é garantido que os números pseudo-aleatórios usados ​​na prática funcionem na teoria; tudo o que sabemos é que eles parecem funcionar empiricamente. (Na verdade, a maioria dos PRNGs realmente em uso pode ser quebrado, para que eles não são realmente seguros para o uso em geral, apenas quando você não está tentando especificamente para quebrá-las.)
Yuval Filmus
2
cstheory.se trata de ciência da computação teórica *, não da prática de programação. Goste ou não, as duas áreas são bastante separadas.
Yuval Filmus
2
@YuvalFilmus: O gerador de passo alternado inventado por C. Gunther em 1987 ainda não foi quebrado (ainda não houve quebra pública, e duvido que a NSA também tenha quebrado). Vinte e oito anos é muito tempo para permanecer ininterrupto, estou surpreso que um gerador tão simples (três LFSRs e um portão XOR, quão simples é isso?) Ainda não foi quebrado e não é usado com mais frequência.
William Hird
2
@ WilliamHird: Dependendo da definição de "quebrado", ele parece ter sido quebrado (mais ou menos na mesma proporção da família A5 / x relacionada, mais eficiente e amplamente usada). Consulte crypto.stackexchange.com/a/342 .
Emil Jeřábek apoia Monica