Para quais algoritmos existe uma grande lacuna entre a análise teórica e a realidade?

52

Duas maneiras de analisar a eficiência de um algoritmo são:

  1. colocar um limite superior assintótico em seu tempo de execução e
  2. executá-lo e coletar dados experimentais.

Gostaria de saber se existem casos conhecidos em que existe uma lacuna significativa entre (1) e (2). Com isso, quero dizer que (a) os dados experimentais sugerem um assintótico mais rígido ou (b) existem algoritmos X e Y, de modo que a análise teórica sugere que X é muito melhor que Y e os dados experimentais sugerem que Y é muito melhor que X.

Como as experiências geralmente revelam um comportamento de caso médio, espero que as respostas mais interessantes se refiram aos limites superiores de caso médio. No entanto, não quero descartar respostas possivelmente interessantes que falem sobre limites diferentes, como a resposta de Noam sobre o Simplex.

Inclua estruturas de dados. Por favor, coloque um algo / ds por resposta.

Radu GRIGore
fonte
Ajudaria se você esclarecesse que tipo de limites superiores você está falando. Você está falando apenas de problemas para os quais existe uma lacuna significativa entre os limites superior e inferior mais conhecidos para a pior complexidade do tempo? Ou você também está incluindo problemas nos quais são conhecidos limites apertados na pior complexidade do tempo, mas os tempos de execução típicos são significativamente mais rápidos? Pode ser mais interessante considerar a complexidade suavizada em vez da complexidade do pior caso. Resultados experimentais de entradas 'típicas' ou entradas aleatórias fazem pouco para provar a existência de entradas patológicas.
James King
Nesse caso, acho que há duas perguntas que devem ser feitas separadamente: uma sobre lacunas entre a complexidade do pior caso e a complexidade do caso médio / suavizado, e outra sobre as lacunas entre a complexidade do caso médio / suavizado teórica e os resultados experimentais práticos. Edit: você fez uma edição abordando isso enquanto eu estava escrevendo meu comentário :)
James Rei

Respostas:

37

O exemplo mais flagrante é, obviamente, o método Simplex, que é executado rapidamente na prática, sugerindo polimetemporalidade, mas leva tempo exponencial na teoria. Dan Spielman acabou de receber o prêmio Nevanlinna em grande parte por explicar esse mistério.

De maneira mais geral, muitas instâncias da programação inteira podem ser resolvidas muito bem usando solucionadores de IP padrão; por exemplo, leilões combinatórios para a maioria das distribuições tentadas em entradas de tamanho significativo podem ser resolvidos - http://www.cis.upenn.edu/~mkearns /teaching/cgt/combinatorial-auctions-survey.pdf

Noam
fonte
3
Foi encontrada uma família explícita de programas lineares para os quais o simplex leva tempo exponencial?
Opte
11
Tanto quanto eu entendo, existem muitas famílias explícitas que requerem tempo exponencial (por exemplo, o primeiro dado por Klee e Minty: "Quão bom é o algoritmo simplex?", 1972). No entanto, a escolha da regra de pivô é relevante para esses resultados. Eu acho que a maioria das referências a esses resultados pode ser encontrada no artigo de Spielman e Teng ( arxiv.org/abs/cs/0111050 ).
MRA
há lowerbounds para alguma regra giro específica neste trabalho cs.au.dk/~tdh/papers/random_edge.pdf
Igor Shinkar
26

Bases de Groebner . O pior caso de tempo de execução é duplamente exponencial (no número de variáveis). Na prática, no entanto, especialmente para problemas bem estruturados, os algoritmos F4 e F5 são eficazes (ou seja, terminam rapidamente). Ainda é uma área ativa de pesquisa para descobrir qual deve ser a conjectura adequada em relação ao tempo médio ou esperado de execução. Supõe-se que esteja relacionado, de alguma forma, ao volume do pólipo de Newton do ideal subjacente.

Jacques Carette
fonte
Média / esperado em que distribuição? Eu pensei mesmo definir o tempo de execução esperado era difícil para problemas algébricos ...
Joshua Grochow
11
Não conheço os casos resolvidos rapidamente pelos métodos F4 e F5, mas é muito fácil criar um sistema de polinômios com muitas variáveis ​​e baixo grau que codificam uma instância SAT. Nesse caso, não me é conhecido que o algoritmo supera o DPLL / DPLL +. Eu realmente gostaria de saber mais sobre os resultados experimentais sobre essas coisas!
MassimoLauria
@ Josué: neste momento, qualquer distribuição que permita resultados ... @Massimo: problema de codificação X como uma instância de Y quase nunca supera algoritmos especializados para X! Mas GB e DPLL são essencialmente equivalentes, então eu ficaria surpreso ao ver uma diferença efetiva.
Jacques Carette
11
@ Massimo: Sim, o cálculo do GB é NP-Hard. Dependendo da formulação. De fato, a maioria das perguntas (preenchimento, associação ideal, campo algebricamente fechado x booleanos) é PSPACE completa ou pior (EXPSPACE completa). O que quer dizer que se espera que os cálculos de GB sejam muito mais difíceis que os problemas completos de NP (e, portanto, em média, qualquer algoritmo para eles como o F5 provavelmente não superará o DPLL).
Mitch
22

Um exemplo excelente e pouco reconhecido desse fenômeno é o isomorfismo gráfico . O algoritmo mais conhecido leva algo como tempo , mas o isomorfismo do gráfico tende a ser resolvido rapidamente na prática. O(2((nlogn)))

Não sei se há um resultado formal na complexidade média / suavizada do problema, mas lembro-me de ler que ele existia - talvez alguém consiga apontar um resultado formal. Certamente, existem muitas evidências experimentais e muitos solucionadores rápidos. Também estou curioso para saber se essa propriedade se estende a outros membros da família GI-complete.

Anand Kulkarni
fonte
11
Não conheço nenhuma análise otimizada para o IG - ou mesmo como seria exatamente - mas há uma análise da implementação prática mais conhecida (nauty) que mostra que ela é executada no pior dos casos. Obviamente, o nauty não está implementando o algoritmo . Consulte cstheory.stackexchange.com/questions/3128/… para obter uma referência. O(2nlogn)
21910 Joshua Grochow
2
Oh! Talvez você esteja pensando de Babai-Kucera, o que dá um algoritmo de caso médio em tempo linear para GI: doi.ieeecomputersociety.org/10.1109/SFCS.1979.8
Joshua Grochow
Sim, Babai-Kucera é quem escolhe! Obrigado pela referência.
Anand Kulkarni
20

De David Johnson, uma discrepância nas proporções de aproximação teórica versus experimental: O problema do vendedor ambulante: um estudo de caso em otimização local, DS Johnson e LA McGeoch . Neste artigo, eles fornecem evidências experimentais de assintóticos (uma vez que os experimentos atingem o tamanho N = 10.000.000!) Que desafiam os assintóticos teóricos: o algoritmo "Greedy" ou "Multi-Fragment" de Jon Bentley (pior dos casos, razão de aproximação pelo menos logN / loglogN) supera a inserção mais próxima e o MST duplo, ambos com taxas de aproximação de pior caso de 2.

Joshua Grochow
fonte
20

Outro exemplo que não foi bem entendido até recentemente é o tempo de execução do algoritmo k-means de Lloyd , que (do ponto de vista prático) é o algoritmo de cluster escolhido por mais de 50 anos. Somente recentemente, em 2009, foi provado (por Vattani ) que, na pior das hipóteses, o algoritmo de Lloyd exige uma série de iterações exponenciais no número de pontos de entrada. Por outro lado, ao mesmo tempo, uma análise suavizada (de Arthur, Manthey e Röglin ) provou que o número suavizado de iterações é meramente polinomial, o que explica o desempenho empírico.

MRA
fonte
10

Os corolários transversais, deque e divididos da conjectura de otimalidade dinâmica para árvores de espalhamento são exemplos dessas lacunas. As experiências apoiam a reivindicação de tempo linear, mas não há prova conhecida.

Radu GRIGore
fonte
3
Seth Pettie provou que as operações n deque não levam mais que O (n alpha * (n)), onde "alpha *" é a função Ackermann inversa iterada, que é uma lacuna bastante pequena.
Jbapple
9

Há um pequeno problema com a pergunta. De fato, existem mais de duas maneiras de analisar um algoritmo, e uma das maneiras teóricas que foram negligenciadas é o tempo de execução esperado, em vez do pior dos casos. É realmente esse comportamento médio de caso que é relevante para fazer experimentos. Aqui está um exemplo muito simples: imagine que você tenha um algoritmo para uma entrada de tamanho n, que leva tempo n para cada entrada possível de tamanho n, exceto por uma entrada específica de cada comprimento que leva tempo 2 ^ n. Ouça que o pior caso de tempo de execução é exponencial, mas o caso médio é [(2 ^ n -1) n + (2 ^ n) 1] / (2 ^ n) = n - (n-1) / 2 ^ n que limites para n. Claramente, os dois tipos de análise fornecem respostas muito diferentes, mas isso é de se esperar, pois estamos calculando quantidades diferentes.

Ao executar o experimento várias vezes, mesmo se levarmos o tempo de execução mais longo para a amostra, ainda estamos amostrando apenas uma pequena parte do espaço de entradas possíveis e, portanto, se casos difíceis forem raros, provavelmente sentiremos falta deles .

É relativamente fácil construir esse problema: se os primeiros n / 2 bits forem zero, resolva a instância 3SAT codificada com os últimos n / 2 bits. Caso contrário, rejeite. À medida que n cresce, o problema tem aproximadamente o mesmo tempo de execução no pior dos casos, como o algoritmo mais eficiente para o 3SAT, onde o tempo médio de execução é garantido muito baixo.

Joe Fitzsimons
fonte
Eu já respondi a James King acima que estou esperando que as respostas mais interessantes sejam sobre o tempo de execução esperado. Vou editar a pergunta para tornar isso mais visível.
Radu GRIGore
9

A inferência do tipo Damas-Milner é comprovadamente completa por tempo exponencial e existem casos de construção fácil com explosão exponencial do tamanho de um resultado. No entanto, na maioria dos insumos do mundo real, ele se comporta de maneira efetivamente linear.

sclv
fonte
Existe uma referência que você recomendaria para este resultado? Eu gostaria de ler mais sobre isso.
Radu GRIGore
11
Eu mesmo não li, mas o artigo mais frequentemente citado é Harry G. Mairson, "A decidibilidade da tipagem ML é completa por tempo exponencial determinístico", 17º Simpósio de Princípios de Linguagens de Programação (1990).
SCLV
9

A árvore PTAS para Steiner em gráficos planares tem uma dependência ridícula do epsilon. No entanto, há uma implementação que mostra um desempenho surpreendentemente bom na prática.

zotachidil
fonte
8

Heaps de emparelhamento, de [1] - eles implementam heaps, onde inserir e mesclar têm O (log n) complexidade amortizada, mas são conjecturados como O (1). Na prática, eles são extremamente eficientes, especialmente para usuários de mesclagem.

Acabei de descobri-los hoje mesmo ao ler o Sec. 5.5 do livro de C. Okasaki "Estruturas de dados puramente funcionais", então pensei em compartilhar informações sobre elas.

[1] Fredman, ML, Sedgewick, R., Sleator, DD e Tarjan, RE 1986. A pilha de emparelhamento: uma nova forma de pilha de autoajuste. Algorithmica 1, 1 (Jan. 1986), 111-129. DOI = http://dx.doi.org/10.1007/BF01840439

Blaisorblade
fonte
Houve alguns avanços desde Okasaki, e agora existem emparelhamentos (imperativos) com O (0) meld, O (1) insert e findMin, O (lg lg n) decrescenteKey e O (lg n) deleteMin: arxiv. org / abs / 0903.4130 . Esse heap usa um mecanismo de emparelhamento diferente dos heaps de emparelhamento originais de Fredman et al.
Jbapple #
7

Relacionado à observação de ilyaraz sobre ramo e limite, Pataki et al. mostre que a redução de base de ramificação e de ligação e de rede pode resolver quase todos os IPs aleatórios no polytime.

Marco
fonte
6

A heurística de Lin-Kernighan para o TSP ("Uma heurística eficaz para o problema do vendedor ambulante", Operations Research 21: 489-516, 1973) é muito bem-sucedida na prática, mas ainda carece de uma análise de caso médio ou suavizada para explicar seu desempenho . Em contraste, há uma análise suavizada da heurística 2-opt para o TSP por Matthias Englert, Heiko Röglin e Berthold Vöcking (Algorithmica, para aparecer).

Bodo Manthey
fonte
5

Na prática, existem muitos algoritmos de ramificação e limite muito rápidos e eficientes para diferentes problemas difíceis de NP que não podemos analisar rigorosamente: TSP, árvore Steiner, empacotamento de caixas e assim por diante.

Ω(nm)

ilyaraz
fonte
Você quer dizer O (mn), ou estou confuso?
Radu GRIGore
O(nmlog(n2/m))