Estou tentando criar uma lista de algoritmos / problemas que são "excepcionalmente úteis", como resolver problemas que 'parecem' muito exponenciais por natureza, mas que têm algum algoritmo particularmente inteligente que finalmente os resolve. Exemplos do que quero dizer:
- Programação Linear (O algoritmo simplex é tempo exponencial; demorou muito tempo para encontrar uma solução de tempo polinomial!)
- De maneira mais geral, Programação Semidefinida
- Teste de primazia
- 2-SAT e HORNSAT
- Determinantes da computação (se isso não parecer difícil, considere o permanente)
- Encontrar combinações perfeitas
- Uma variedade de problemas teóricos de grupos difíceis que podem ser realizados usando a Classificação de grupos simples finitos
- Uma variedade de problemas gráficos difíceis que podem ser resolvidos usando caracterizações Menores Proibidas Menores (incorporação em uma superfície arbitrária; delimitação de largura de árvore e largura de filial; gráficos redutíveis Delta-Wye)
- Computando exponenciais em um grupo delimitado (isto é, computando em \ log b etapas, como realizado por quadrados repetidos)
- Cálculos baseados no algoritmo LLL. (Como um caso especial: algoritmo euclidiano. Como um caso mais geral: algoritmos PSLQ ou HJLS.)
- Problemas de restrição sem termos de Taylor (?). Admito que não entendo completamente isso, mas parece que provavelmente inclui os casos 2-SAT / HORNSAT acima e qualquer álgebra linear sobre campos finitos. Veja aqui para uma postagem mais longa
- Problemas computáveis através de reduções holográficas .
Como menção honrosa, eu também mencionaria o isomorfismo do gráfico, porque ainda é muito fácil ( ), e equivalente a muitos outros problemas de isomorfismo:
- Dígrafos / multigráficos / hipergráficos (uma espécie de problema "mais difícil")
- Autômatos finitos / CFGs
Obviamente, há uma série de dificuldades nisso, mas todas deixam pelo menos algumas pessoas com um certo senso de 'surpresa', no sentido de que o problema pode parecer difícil, mas se torna tratável. O LP pode parecer relativamente simples, mas as pessoas demoraram um pouco para criar uma solução real. A repetição de quadrados ou a solução de 2-SAT é algo que um aluno de graduação pode inventar por conta própria, mas se você tivesse aprendido apenas sobre os problemas do NP-Complete sem ter visto o HORNSAT, isso poderia soar como um candidato natural à completude do NP. Resolver o CFSG ou ter uma maneira polinomial de verificar a redutibilidade do Delta-Wye não é uma proeza.
Espero que isto faça sentido; Obviamente, existem muitos atributos subjetivos aqui, mas estou curioso para saber o que outras pessoas consideram soluções eficientes para problemas "obviamente difíceis".
fonte
Respostas:
Para mim, um dos algoritmos mais eficientes é o algoritmo Blossom V, que encontra a correspondência perfeita de peso máximo em um gráfico geral:
https://en.m.wikipedia.org/wiki/Blossom_algorithm
fonte
Para mim, todos os algoritmos clássicos e os mais eficientes, mais recentes , para verificar ou encontrar uma árvore de abrangência mínima (MST) de um gráfico com borda ponderada conectada são bons candidatos. Muitos desses algoritmos estão listados na wikipedia .
À primeira vista, esse problema parece o problema do vendedor ambulante, um dos poucos problemas mais difíceis de NP. Surpreendentemente, existem algoritmos lineares para verificar um MST e muitos algoritmos quase lineares para encontrar um MST! De fato, um dos problemas abertos mais famosos dos algoritmos é se existe um algoritmo linear determinístico para encontrar um MST em gráficos gerais. Acontece que existem estruturas e propriedades ricas em matemática e gráficos, além de uma infinidade de aplicativos práticos associados ao MST, tornando-o um dos tópicos mais agradáveis e expansíveis no curso de ciência da computação. Para uma introdução abrangente um pouco desatualizada, mas muito bem escrita, consulte o tutorial de Jason Eisner .
fonte