Algoritmos poderosos muito complexos para implementar

67

Quais são alguns algoritmos de utilidade legítima que são simplesmente muito complexos para implementar?

Deixe-me esclarecer: não estou procurando algoritmos como o atual algoritmo de multiplicação de matriz assintótica ideal (Coppersmith-Winograd), que é razoável de implementar, mas tem uma constante que o torna inútil na prática. Estou procurando algoritmos que possam ter um valor prático plausível, mas que são tão difíceis de codificar que nunca foram implementados, apenas implementados em configurações extremamente artificiais ou implementados apenas para aplicativos de propósito especialmente extraordinário.

Também são bem-vindos algoritmos quase impossíveis de implementar, com bons assintóticos, mas provavelmente com desempenho real ruim.

ds.algorithms ds.data-structures big-list implementation Elliot Jans
fonte
11
fazendo essa CW, já que poderia ser uma lista longa.
Suresh Venkat
4
Existe uma métrica para 'quase impossível de implementar'? Existe uma teoria que a define?
Ritwik Bose
@ Mecko, talvez um limite mais baixo do tamanho da menor máquina de Turing que produz uma descrição de uma máquina de Turing que é uma implementação do algoritmo. :)
Radu Grigore
@Radu GRIGore Essa é uma métrica aceita ou que deve ser desenvolvida? Suponho que (por agora) há uma linha simples, imóvel que define 'meh, não vale a pena' ...: D
Ritwik Bose
4
Estou interessado na sugestão de que o Coppersmith-Winograd é razoável de implementar. Alguém já viu uma implementação escrita, mesmo em pseudo-código de alto nível, e alguém já estimou as constantes?
Raphael

Respostas:

33

Chazelle deu um algoritmo de tempo linear para triangular um polígono simples . Skiena escreveu (p.575, Manual de Projeto de Algoritmos) que é "suficientemente inútil implementar que se qualifique mais como prova de existência"

Yaroslav Bulatov
fonte
3
O algoritmo possui constantes razoáveis?
jbapple
Esse é o único algoritmo de tempo linear conhecido para o problema?
Thomas Ahle
2
@ThomasAhle Eu acredito que é o único algoritmo de tempo linear determinístico conhecido. Amato, Goodrich, e Ramos ter um simples randomizado um: cs.princeton.edu/courses/archive/fall05/cos528/handouts/...
Sasho Nikolov
O algoritmo de triangulação simples de polígonos no tempo linear de Chazelle, que eu saiba, nunca foi implementado e provavelmente nunca será por causa de sua complexidade e também porque as constantes são altas, de modo que não será capaz de competir com alternativas na prática. Grande conquista teórica embora. Ralph Boland
Ralph Boland
Vou perguntar novamente: o algoritmo tem constantes razoáveis?
User1271772
29

O algoritmo Risch para calcular antiderivadas elementares. Segundo a Wikipedia, nenhum pacote de software é conhecido por implementar o algoritmo completo devido à sua complexidade.

Mark Reitblatt
fonte
3
A Wikipedia também aponta que este não é um algoritmo, mas um semi-algoritmo, porque requer heurísticas para resolver o problema constante.
SCLV
O que é heurística? Você pode dar um link para ler mais sobre isso?
Zygimantus
22

Qualquer algoritmo que use os resultados de Robertson-Seymour para inferir um algoritmo "polytime" para coisas que envolvam gráficos que excluem um menor fixo está pedindo problemas. A constante oculta em seu resultado é "galáctica".

Suresh Venkat
fonte
3
Isso também é difícil de implementar ou tem uma constante enorme?
Lev Reyzin
5
Sim, isso não parece um bom exemplo. Se bem entendi, a questão é sobre algoritmos que podem ser práticos (portanto, constantes "pequenas"), mas são complexos demais para serem implementados. Naturalmente, toda a questão está aberta a diferentes interpretações :-)
Aryabhata
5
O problema é que a constante vem da lista muito grande de menores que é preciso excluir para uma propriedade específica. Não conheço nenhuma maneira de gerar a lista desejada de menores excluídos para uma determinada propriedade, portanto, não é apenas um problema de escala.
Suresh Venkat
2
Por exemplo, nem sequer sabemos a lista de menores excluídos para gráficos incorporáveis ​​no toro.
Derrick Stolee
17
O problema aqui parece mais profundo: não existe uma maneira eficaz de gerar a lista de menores, portanto, na verdade, isso não gera um algoritmo. A maioria das propriedades fechadas menores produz uma lista infinita de menores excluídos, se alguém traduzir diretamente a expressão lógica. O Teorema de Robertson-Seymour (Conjectura de Wagner) nos diz que uma lista finita de menores excluídos está à espreita dentro dessa lista infinita, mas o teorema não ajuda em nada a encontrá-los. Portanto, Robertson-Seymour geralmente leva a uma pura prova de existência.
András Salamon
16

O(n)O(log2⁡nB)B

O artigo tem 55 páginas e sua conclusão observa várias melhorias nas constantes que o autor não descreve por razões de espaço. Isso me faz suspeitar que talvez as constantes não sejam tão galácticas e que essa estrutura de dados seja de "utilidade legítima", principalmente porque já foi citada várias vezes.

jbapple
fonte
12

O algoritmo de unificação de padrões de ordem superior de tempo linear por Qian nunca foi implementado devido à sua complexidade AFAIK.

Dominic Mulligan
fonte
Felizmente, ainda existem algoritmos práticos. O manual do raciocínio automatizado diz que isso pode ser feito no polytime (ao lado de onde ele cita o algoritmo de Qian), o que é bastante impressionante.
Jake
11

Algoritmo de tempo linear para verificar se um gráfico pode ser incorporado em uma superfície fixa.

Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed: Um algoritmo de tempo linear mais simples para incorporar gráficos em uma superfície arbitrária e o gênero de gráficos de largura de árvore limitada. FOCS 2008: 771-780.

Bojan Mohar: um algoritmo de tempo linear para incorporar gráficos em uma superfície arbitrária. SIAM J. Matemática Discreta. 12 (1): 6-26 (1999)

alguém
fonte
11
É improvável que tenha valor prático, mesmo se implementado, devido à grande dependência exponencial (sic) do gênero.
Jeffε
8

Não tenho certeza de quão útil poderia ser na prática (embora esteja pensando em dobrar e comparar proteínas, bem como na previsão da estrutura secundária do RNA), mas Wolfgang Haken deu o primeiro algoritmo de tempo polinomial para decidir se um nó é um nó. loop simples ( Theorie der Normalflächen. Acta Math. 105, 1961, pp. 245-375). Pelo que me lembro, ainda é muito complicado para ser implementado todas essas décadas depois.

Para acreditar na Wikipedia, vários outros algoritmos foram dados posteriormente, e "Compreender a complexidade desses algoritmos é um campo de estudo ativo".

Anthony Labarre
fonte
4
Haken deu o primeiro algoritmo, mas não é executado no tempo polinomial; de fato, nenhum algoritmo poli-tempo (ou resultado de dureza NP) é conhecido. Trabalhos mais recentes reduziram a trivialidade do nó (através da formulação de superfície normal de Haken) à programação inteira, que geralmente é rápida de resolver na prática.
Jeffε
3

Decomposição de árvores e talvez montes de Fibonacci .

Peter Boothe
fonte
14
Montes de Fibonacci certamente não são muito complicados de implementar; eles foram implementados e testados. O problema deles é que seu desempenho prático não é tão bom quanto alguns outros montes devido a fatores constantes em seu tempo de execução.
David Eppstein
11
Eu escrevi um pacote para encontrar decomposição árvore, e eu não acho que é difícil de implementar yaroslavvb.blogspot.com/2011/01/building-junction-trees.html
Yaroslav Bulatov
2
Meu código é apenas uma decomposição de árvore heurística, não é ideal como abordagens de programação dinâmica e ramificada ... Acho que você quis dizer "Um algoritmo de tempo linear ..." de Bodlaender? Eu não vi nenhuma implementação disso
Yaroslav Bulatov
4
2O(k3)O(n)
3
Acho que este é o melhor esforço de implementação: hein.roehrig.name/dipl
Diego de Estrada
1

A construção perfeita de hash ( https://en.wikipedia.org/wiki/Perfect_hash_function#Construction ) se aplicaria a qualquer caso de uso com chaves estáticas ou com alterações pouco frequentes (por exemplo, nomes de domínio de nível superior em roteadores, palavras-chave em compiladores ou nomes de funções em bibliotecas padrão), mas a última vez que olhei não consegui encontrar nenhuma implementação.

A pesquisa paramétrica pode resolver muitos problemas difíceis de otimização, incluindo alguns que podem parecer difíceis de NP, em tempo polinomial. O bem-nomeado trabalho de pesquisa paramétrica tornou os implementos práticos uma variante da pesquisa paramétrica, mas ainda não acho que tenha sido implementado em software prático.

knO(nlog⁡n+k)O((n+k)log⁡n)

Kevin A. Wortman
fonte
11
Eu me recuso a acreditar que a construção do FKS é muito complexa para implementar. Na verdade, é bastante direto. Talvez não seja prático, mas certamente não muito complexo para implementar.
Sasho Nikolov