Algoritmo aleatório que "parece" determinístico?

31

Existe um exemplo interessante de um algoritmo aleatório para um problema de pesquisa que sempre gera a mesma resposta (correta), independentemente de sua aleatoriedade interna, mas que explora a aleatoriedade para que seu tempo de execução esperado seja melhor que o tempo de execução do mais rápido conhecido algoritmo determinístico para o problema?

Em particular, eu queria saber se existe um algoritmo para encontrar um primo entre n e 2n. Não há algoritmo determinístico de tempo polinomial conhecido. Existe um algoritmo aleatório trivial que funciona apenas amostrando números aleatórios no intervalo, que funciona graças ao teorema do número primo . Mas existe um algoritmo do tipo acima cujo tempo de execução esperado é intermediário entre os dois?

EDIT: Para refinar um pouco a minha pergunta, eu queria um algoritmo para um problema em que houvesse muitas saídas corretas possíveis e, no entanto, o algoritmo aleatório decidisse por um independente de sua aleatoriedade. Sei que a pergunta provavelmente não está totalmente especificada ...

arnab
fonte
3
Para fornecer algumas palavras-chave de pesquisa, algoritmos aleatórios que sempre produzem a resposta correta (e usam aleatoriedade para reduzir o tempo de execução) são chamados algoritmos de Las Vegas (ao contrário dos algoritmos de Monte Carlo) ou algoritmos de erro zero, e uma classe de complexidade relacionada é ZPP .
Tsuyoshi Ito
@ Tsuyoshi: Obrigado pelo seu comentário. Mas não estou ciente dos algoritmos do tipo Las Vegas para problemas de pesquisa. Esta é a minha pergunta.
arnab
Se houver um algoritmo aleatório para encontrar equilíbrios únicos de Nash, isso responderia sua pergunta.
Warren Schudy
Talvez haja algum problema relacionado a ataques de aniversário ( en.wikipedia.org/wiki/Birthday_attack ) que atendam às suas necessidades?
Warren Schudy

Respostas:

23

Shafi Goldwasser me comunicou que ela e seus co-autores estão investigando exatamente esses algoritmos para problemas teóricos dos números! O seguinte é conhecido:

  1. Lenstra mostrou que existe um algoritmo para encontrar um mod quadrático sem resíduo em um dado primo.

  2. Gat e Goldwasser mostraram que existe um algoritmo para encontrar um gerador de , em que é um dado primo da forma para um primo . p2q+1qZpp2q+1q

(Não conheço referências citáveis.) Também há pesquisas em andamento sobre a pergunta que fiz sobre encontrar um primo entre e .2 nn2n

EDIT: O artigo de Gat e Goldwasser está agora publicado: http://eccc.hpi-web.de/report/2011/136/ . Este artigo, porém, não resolve a questão de encontrar um primo entre e .2 nn2n

arnab
fonte
1
+1 virtual. Isso é realmente interessante, vai olhar para o papel.
András Salamon
2
Apesar da nota, votei esta resposta simplesmente porque esta é uma boa resposta. Não acho que haja algo errado em votar uma boa resposta postada para outra pessoa. Comecei uma discussão no Meta sobre isso.
Tsuyoshi Ito
1
Eu removi a nota e a criei como "wiki da comunidade", conforme a discussão no meta-thread.
arnab
O meta thread mencionado por arnab pode ser encontrado aqui: meta.cstheory.stackexchange.com/q/607/873 .
MS Dousti
18

As estruturas de dados aleatórios contam?

Existe a lista de pulos, que é uma estrutura de dados do mapa associativo classificado.

Seu tempo de execução para operações comuns, como inserção, recuperação e exclusão, é (no caso esperado) igual ao das árvores de pesquisa balanceadas - ou seja, . No entanto, às vezes se afirma que a estrutura de dados tem um fator constante muito melhor do que as implementações da árvore de pesquisa quando feitas corretamente (isso depende criticamente de uma fonte boa e eficiente de aleatoriedade). O melhor fator constante provavelmente resulta do fato de que nenhum reequilíbrio (ou qualquer operação semelhante) deve ocorrer.O(logn)

Konrad Rudolph
fonte
Obrigado! Definitivamente, isso conta e é uma resposta não trivial à minha pergunta original. Eu queria um problema, embora mais análogo ao problema de localização privilegiada, onde existem muitas soluções em potencial.
arnab
Adicione listas de atalhos a essa linha de pensamento.
Raphael
13

E o algoritmo simplex de tempo polinomial aleatório de Kelner e Spielman? Encontra o vértice ideal de um programa linear. Não se conhece nenhum algoritmo simplista determinístico que seja comprovadamente executado em tempo polinomial e, para muitos deles, podem ser construídas instâncias patológicas que fazem o algoritmo levar um tempo exponencial.

Obviamente, existem algoritmos de ponto interior em tempo polinomial, portanto não é exatamente o que você está procurando.

Peter Shor
fonte
Se existem vários pontos ótimos, Kelner-Spielman sempre retornaria o mesmo ponto?
Sasho Nikolov
3
Os programas lineares genéricos têm apenas um ponto ideal; portanto, usando perturbação, uma variante de Kelner-Spielman pode ser feita que sempre retorna o mesmo ponto ideal.
quer
12

Considere uma árvore binária completa com todas as folhas contendo 0, exceto uma folha que contém 1. A tarefa é encontrar a folha que contém 1. Em qualquer algoritmo de pesquisa determinístico, é possível construir uma família infinita de árvores (uma para cada n ) para o qual o algoritmo deve verificar todas as folhas. Portanto, para essa família de pior caso, o algoritmo determinístico esperava o tempo de execução 2 n .2nn2n

Agora considere um algoritmo que escolhe aleatoriamente a primeira folha de maneira aleatória e, em seguida, verifica todas as folhas sucessivas deterministicamente (envolvendo o início). Isso encontrará o 1 após examinar a metade de todas as folhas, em média. Portanto, o algoritmo aleatório esperava o tempo execução 2 n - 1 .2n1

Isso se qualifica?

András Salamon
fonte
Agradável!! Isso definitivamente se qualifica, embora eu estivesse procurando um exemplo não trivial, em que a melhoria no tempo de execução fosse mais substancial.
arnab
Você não precisa da estrutura em árvore, isso funciona em uma matriz.
Sdcvvc
7

Fplogpp

logp

Srikanth
fonte
6

Havia um projeto polímata abordando uma questão relacionada: http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

Anthony Leverrier
fonte
Sim, essa foi uma fonte de motivação para eu fazer a pergunta. Eu não acho que eles mencionaram explicitamente essa questão no projeto polímata.
arnab
3

Em relação à sua primeira pergunta, pensei no Quicksort primeiro, mas isso deve ser óbvio.

Existe um algoritmo de correspondência de strings ( Nebel, 2006 ) que utiliza idéias probabilísticas. Eu sei se essa é a abordagem mais rápida existente, e você aparentemente precisa de algumas amostras para treinamento.

Rafael
fonte
A descoberta mediana também é mais rápida, mas não de forma dramática.
Aram Harrow
3

O seguinte documento do STACS '97 pode ser interessante para o seu caso: A complexidade da geração de instâncias de teste .

Resumo: Recentemente, Watanabe propôs uma nova estrutura para testar a correção e o comportamento médio de caso de algoritmos que pretendem resolver um determinado problema de pesquisa de NP com eficiência em média. A idéia é gerar aleatoriamente instâncias certificadas de maneira que se assemelhe à distribuição subjacente. Discutimos essa abordagem e mostramos que instâncias de teste podem ser geradas para todos os problemas de pesquisa do NP com consultas não adaptáveis ​​a um oracle do NP. Além disso, apresentamos os tipos de geradores de instância de teste de Las Vegas e Monte Carlo e mostramos que esses geradores podem ser usados ​​para descobrir se um algoritmo está correto e eficiente em média. De fato, não é difícil construir geradores Monte Carlo para todos os problemas de pesquisa de RP, assim como geradores de Las Vegas para todos os problemas de pesquisa de ZPP. Por outro lado,

Especialmente, veja a página 384, no Corolário 12:

ZPPRPZPPNPNPcoNP

MS Dousti
fonte
2

1ncpolylog(n)

Ramprasad
fonte
3
Isto refere-se ao teste e não encontrar ...
Dana Moshkovitz
Eu estava interessado mais em problemas de pesquisa. Para problemas de decisão, existem algoritmos de Las Vegas.
arnab