Teoria decente do crescimento assintótico

12

Quais são os limites conhecidos da decidibilidade da comparação da taxa de crescimento de funções de ? Estou aqui pensando na decidibilidade de perguntas como "Is x x2 x lg ( x + 2 ) ?" ou "é 2 lg * xO ( lg lg x ) ?".NNxx2xlg(x+2)2lgxO(lglgx)

Se restringimos as funções a serem polinômios (expressos da maneira usual), isso não é difícil. Veja também o formulário normal do Cantor .

Qual é o tamanho da classe de funções antes que a comparação se torne indecidível? Podemos estendê-lo às funções usadas em uma classe típica de algoritmos de graduação?

Como Joshua Grochow explica nos comentários, estou realmente interessado no conjunto de expressões, não nas próprias funções. Assim, por exemplo, eu estaria interessado em procedimentos de decisão que pudessem comparar " " e " 2 ", mesmo que não consigam comparar " ln e " e " n ( ln n ) - 1 ".12lnen(lnn)1

Pergunta possivelmente relacionada: "A teoria dos limites assintóticos é finitamente axiomatizável?"

jbapple
fonte
2
Pergunta interessante! Eu acho que uma parte deve ser mudada um pouco. Não acho que a pergunta deva ser qual é o tamanho da classe de funções, mas como as funções são expressas . Ou seja, se você receber duas máquinas de Turing em tempo polinomial como entrada, é indecidível dizer qual delas possui um tempo de execução maior (apesar do fato de ambas terem tempos de execução polinomiais) ... Se essas funções foram expressas como, digamos , polinômios explícitos (escreva todo o poli com coeficientes), então é fácil comparar.
Joshua Grochow
Bom ponto. Você tem alguma sugestão sobre como expressar isso?
Jbapple
1
Eu acho que depende do que você está interessado. Pode ser natural solicitar funções expressas como fórmula envolvendo várias operações, e então a pergunta é: quais conjuntos de operações a tornam decidível / indecidível. por exemplo, operações incluem +, tempos, dividir, -, enésimas raízes, exp, log, composição, log ^ *, etc. (Se você deixar de fora o log ^ *, a lista anterior
fornecerá

Respostas:

9

Rxexplog||f(x)5+f(x)=xestá na família). Hardy mostrou que qualquer uma dessas duas funções pode ser comparada assintoticamente. Não tenho certeza se a prova é algorítmica, mas vale a pena conferir.

Boshernitzan estendeu essa classe ainda mais e, sem dúvida, há outros trabalhos sobre o assunto.

Yuval Filmus
fonte
O livro de John R. Shackell "Asymptotics Simbólico" afirma (seção 5.1, página 91), que o primeiro algoritmo para esse problema foi do artigo de Dahn e Goring de 1986, "Notes on exponential-logarithmic" . A dissertação de Dominik Gruntz, de 1996, "Sobre limites de computação em um sistema de manipulação simbólica" também contém um algoritmo para esse problema e compara vários métodos.
Jbapple
2
No entanto, todos eles contam com um oráculo para resolver o problema da equivalência zero, que é indecidível em geral.
jbapple