Diversão com Ackermann inverso

11

A função inversa de Ackermann ocorre frequentemente ao analisar algoritmos. Uma ótima apresentação está aqui: http://www.gabrielnivasch.org/fun/inverse-ackermann .

α1(n)=[n/2]
α2(n)=[log2n]
α3(n)=logn
...
αk(n)=1+αk(αk1(n))
α(n)=min{k:αk(n)3}

Minha pergunta é: Qual é a função Claramente . Que limites mais estreitos podemos dar em ? É ?

k(n)=min{k:αk(n)k}
1k(n)α(n)k(n)k(n)logα(n)
Dana Moshkovitz
fonte
Eu sei por que , mas você poderia explicar por que é ? k(n)α(n)k(n)α(n)
Jbapple
Ok, editado para o incontroverso . k(n)<α(n)
Dana Moshkovitz
3
@DanaMoshkovitz: Eu aproximadas as definições usando a hierarquia de Ackermann eu sou familiarizados com: e . Com uma definição típica das funções de Ackermann, . Portanto, se então , ou seja, . (Espero não ter cometido um erro lá dentro.)α(n)=min{k:Ak(1)n}k(n)=min{k:Ak(k)n}Ak+1(1)=Ak(Ak(1))Ak(k)Ak(k)nAk+1(1)nk(n)α(n)1
Sylvain
1
@DanaMoshkovitz: para esclarecer, estou usando e , que cresce um pouco mais rápido que sua definição, por exemplo, vez de . Ele não deve ter muito de uma conseqüência porém: e são praticamente a mesma coisa. A1(n)=2nAk+1(n)=Akn+1(1)A2(n)=2n+12nα(n)k(n)
21415 Sylvain
1
@DanaMoshkovitz: Não vejo por que . Para infinitos valores de você terá , ou seja, sempre que ; porque cresce rapidamente, você tem cada vez mais essas seqüências. Com suas definições, é possível ter : portanto mas . k(n)<α(n)nα(n)=k(n)Ak(k)<nAk+1(1)<Ak+1(k+1)Ak+1(1)Ak(k)α(n)<k(n)α2(8)=3>2α(8)=2k(8)=3
22415 Sylvain

Respostas:

12

Seja o inverso de . . Eu afirmo que .AkαkA1(x)=2x,A2(x)=2x,k1(x)=Ax(x)

Como e desde , . Como resultado, .x=αx(Ax(x))z,αy(z)>αx(z)αy(Ax(x))>αx(Ax(x))=xk(Ax(x))=x

Agora considere o valor de . Por definição de , é . Sabemos que , então . Eu afirmo que . . Agora , então . Como , , então . Assim,α(k1(n))=α(An(n))αminz{αz(An(n))3}αn(An(n))=nα(An(n))>nα(An(n))n+2αn+1(An(n))=1+αn+1(n)α(n)=minz{αz(n)3}αα(n)(n)3n+1>α(n)αn+1(n)3αn+1(An(n))4αn+2(An(n))=1+αn+2(αn+1(n))1+αn+2(4)3.

Portanto, temos ; portanto, e são essencialmente iguais.n<α(k1(n))n+2kα

jbapple
fonte
9
E deixe-me acrescentar que todas estas funções são apenas diferentes maneiras complicadas de escrever o número 4.
Sariel Har-Peled
0

Isso está incorreto; veja os comentários.

Uma função muito próxima a essa foi chamada " " e usada nas "Splay Trees, Davenport-Schinzel Sequences e Deque Conjecture de Pettie" , nas quais ele mostrou que " operações de deque [em uma árvore de dispersão] somente tempo, onde é o número mínimo de aplicações da função inversa de Ackermann que mapeia para uma constante ".αnO(nα(n))α(n)n

Essa função é muito lenta e cresce mais lentamente que . Considere a funçãologα(n)f:NN

f(n)={1 n = 02f(n1) n > 0

Essa função cresce aproximadamente tão rapidamente quanto , e cresce mais lentamente que . Agora vou avaliar e em :A(4,n)A(n)=A(n,n)logα(n)α(n)A(f(n))

logα(A(f(n)))=logf(n)=f(n1)

α(A(f(n)))=1+α(f(n))<1+α(A(n))<2+α(n)

Como , cresce muito mais rapidamente do que .f(n1)ω(2+α(n))logα(n)α(n)

jbapple
fonte
Qual é a relação entre alpha ^ * ek (n)? (note que na definição de k (n) eu uso o alpha_k notação (n) definido no link que eu tinha na questão)
Dana Moshkovitz
Desculpe, li seu como ! αkαk
Jbapple