Por que a maioria (ou todos?) Dos algoritmos de tempo polinomial é prática?

Li recentemente um comentário interessante em um artigo sobre como a matemática é estranhamente útil. Menciona como o tempo polinomial não precisa ser eficiente na realidade (por exemplo,$O(n^{999999999999999999999})$é tempo polinomial, mas não eficiente). No entanto, não é o caso de todos os algoritmos em tempo polinomial também serem realistas, como no máximo$O(n^4)$ou alguma coisa? Eu acho que minhas perguntas são:

1. Isso é surpreendente?

2. Existem exemplos de algoritmos com tempo polinomial, mas não práticos?

O comentário está errado. É muito fácil dar exemplos de algoritmos de tempo polinomial que não são práticos:

1. O algoritmo elipsóide para resolver programas lineares é executado em tempo polinomial, mas é muito lento para ser prático. O algoritmo simplex, cujo pior caso de execução é exponencial, é preferido na prática.

2. O algoritmo de teste de primalidade da AKS é executado em tempo polinomial, mas é muito lento para ser prático. Em vez disso, algoritmos de tempo polinomial randomizados são usados. Sacrificamos a certeza pelo desempenho.

3. Os algoritmos de multiplicação de matriz rápida são assintoticamente mais rápidos que a multiplicação de matrizes do ensino médio (ambos são polinomiais), mas são muito lentos para serem práticos. O algoritmo do ensino médio é usado na prática.

4. Um problema semelhante ocorre nos algoritmos de multiplicação rápida de números inteiros. O algoritmo com a melhor complexidade assintótica, o algoritmo de Fürer, é muito lento para ser utilizado na prática. Em vez disso, algoritmos relativamente simples são usados ​​mesmo para números inteiros muito grandes.

5. Os algoritmos de big data precisam ser executados em tempo linearitmico (que é $O(n \log^{O(1)}n)$) para ser prático.

Esses exemplos mostram que a identificação do tempo polinomial com prática não é precisa e pode depender das circunstâncias. Os pesquisadores de algoritmos teóricos sentem necessidade de justificar seu campo de pesquisa e, portanto, acreditam ideologicamente nos sentimentos expressos no comentário mencionado. Você não deve considerar esses comentários literalmente.

De fato, muitos algoritmos usados ​​na prática são heurísticos e não temos nenhuma estimativa em seu tempo de execução além de resultados empíricos. Esse algoritmo não se encaixa no arcabouço teórico, no entanto, existem muito úteis na prática. Vários algoritmos de aprendizado de máquina (mas não todos) pertencem a essa classe apenas em termos de tempo de execução (sem mencionar em termos de desempenho ), assim como algoritmos de pesquisa como algoritmos de resolução A * e alfa-beta e SAT.

A pergunta (1) é complicada, pela qual nunca vi uma boa razão. Uma sugestão é que é muito mais provável que compreendamos e encontremos as respostas para problemas mais simples; os mais difíceis precisam de habilidades especiais; portanto, a chance de a pessoa certa trabalhar nela e encontrar a resposta é baixa. Tudo isso é muito acenando com a mão.

Para (2) há definitivamente exemplos, de fato, essa pergunta já foi feita e respondida! Observe também que há uma cadeia de links para uma pergunta cstheory.se e uma questão math.se que contêm outros exemplos.

Vi a seguinte explicação sobre sua pergunta (1):

Os poderes de $n$no tempo de execução normalmente surgem de para loops ou construções semelhantes. Cada para circuito por sua vez, é necessário, porque nós, como solucionadores, teve uma idéia de como acabar com o problema ou índice sobre algo útil. Como geralmente usamos apenas um pequeno número de idéias, os poderes tendem a ser pequenos. É difícil imaginar um algoritmo com 20 aninhados para loops, onde, no último loop for , fazemos algo que depende de todos os 20 índices.

Este argumento é atraente para mim, mas é muito fraca porque só lida com para loops. Por exemplo, pode-se facilmente criar qualquer número de aninhados para loops com recursividade, mas, em seguida, pode-se encontrar boas razões contra fazendo uma construção tão bizarra. De qualquer forma, acho que esse argumento pode ser fortalecido com uma análise de muitos casos diferentes, mas apresento apenas a ideia de alto nível.