Você conhece algum problema (de preferência pelo menos um pouco conhecido), onde, para um tamanho de problema prático , um algoritmo exponencial é executado muito mais rápido do que um equivalente de tempo polinomial mais conhecido.
Por exemplo, suponha que um problema tenha um tamanho prático * de e haja dois algoritmos conhecidos: um é 2 n e o outro é n c para alguma constante c . Claramente, para qualquer c > 15 , o algoritmo exponencial é o preferido.
* Acho que tamanho prático significaria algo comumente encontrado no mundo real. Como o número de trens em uma rede.
Respostas:
Que tal o algoritmo simplex para programação linear? Em muitas ocasiões , é usado na prática.
Editado para adicionar: Eu acho que é mais um "algoritmo exponencial de pior caso", que é executado eficientemente em instâncias / distribuições práticas, em vez de ser executado mais rapidamente em instâncias adversárias de tamanho prático .
fonte
fonte
Existem alguns exemplos com detecção / teste de primalidade (não probabilístico / exato) . O algoritmo AKS foi o primeiro algoritmo para teste de primalidade mostrado em P. Ele não compete favoravelmente contra alguns algoritmos de tempo exponencial para entradas "pequenas". Os detalhes são um pouco complicados, porque mostrar isso geralmente requer a implementação de algoritmos, o que é um exercício desafiador e pode depender de aspectos específicos da implementação.
Mais informações / detalhes / referências sobre esta questão cs.se:
fonte