As funções com crescimento mais lento que o Ackermann inverso aparecem nos limites do tempo de execução?

Alguns algoritmos complicados ( união-localização ) têm a função Ackermann inversa quase constante que aparece na complexidade do tempo assintótico e, na pior das hipóteses, o ideal é o pior caso se o termo Ackermann inverso quase constante for ignorado.

Existem exemplos de algoritmos conhecidos com tempos de execução que envolvem funções que crescem fundamentalmente mais lentas que Ackermann inversa (por exemplo, inversões de funções que não são equivalentes a Ackermann sob transformações polinomiais ou exponenciais etc.), que fornecem o pior caso conhecido? complexidade para resolver o problema subjacente?

reference-request algorithm-analysis time-complexity runtime-analysis user2566092
fonte

algoritmos de tempo? Você está perguntando sobre um problema conhecido cujo algoritmo mais conhecido é

? Primeiro, você precisa encontrar uma função que cresça "fundamentalmente mais rápido" que

, como TREE

, depois tome o inverso e, em seguida, encontre um problema que se encaixe nela!

O (1)

$O(1)$

ω (1)

$\omega(1)$

o (α (n))

$o(\alpha(n))$

A (n)

$A(n)$

(n)

$(n)$

GD Pål '

existem algoritmos inventados arbitrárias construídas fora do thm hierarquia de tempo

vzn

@ vzn: Qualquer

não é construtível no tempo (que inclui

). Portanto, o teorema da hierarquia de tempo não pode ser usado aqui.

f (n) = o (n)

$f(n) = o(n)$

α (n)

$\alpha(n)$

Mdxn #

@ MDX feliz que alguém apontou isso, apenas testando você pisca. sim, ultimamente estive pensando que pode haver uma generalização de thm hierarquia de tempo para sub-

funções. mas de qualquer maneira

limite

é porque uma TM construtiva no tempo deve ler toda a entrada, mas estamos dizendo esses outros algoritmos, por exemplo, com complexidade inversa do tempo de Ackermann, não? tendo problemas para visualizar isso! sentir a questão é mais sobre a existência de sub-

línguas .... poderia haver algum tipo de pesquisa ou descrição em algum lugar ....

o (n)

$o(n)$

o (n)

$o(n)$

o (n)

$o(n)$

vzn

DLOGTIME

$\text{DLOGTIME}$

LH

$\text{LH}$

Respostas:

$O(m\log \alpha(m,n))$ $O(m\alpha(m,n))$ $O(m\alpha(m,n))$ O problema de sensibilidade pede para calcular, para um dado gráfico e uma determinada árvore de abrangência mínima, o quanto cada peso de borda pode mudar sem alterar a árvore de abrangência mínima.

(Obrigado a Tsvi Kopelowitz por esta referência.)

Yuval Filmus
fonte

Não sei se o log inverso Ackermann é "fundamentalmente mais lento" do que o inverso Ackermann, mas achei esse tipo de tempo de execução surpreendente.

Yuval Filmus

$\alpha^*(n)$ $n$

templatetypedef
fonte

-1

Quando Alan Turing descobriu o computador, havia vários modelos para o computador proposto. Turing provou que alguns (3) desses modelos poderiam simular-se E calcular a função de Ackermann, enquanto outros modelos poderiam simular-se, mas não a função de Ackermann (para que não pudessem simular o 3). Portanto, esses três modelos (Turing Machine, von Neumann e um que eu não conheço), foram escolhidos como a arquitetura para um computador. Isso não significa que a função Ackermann seja o limite do computador, mas suponho que seja uma ciência difícil. Não conheço nenhuma função computável que cresça mais rápido que a função Ackermann.

Agora, não acho que exista um problema prático que corresponda à sua pergunta, mas talvez possamos construir um. Porém, precisamos colocar restrições na entrada. Como não podemos usar O (n), não podemos verificar toda a entrada. De fato, não podemos nem mesmo verificar o comprimento da entrada, pois seria O (log n). Portanto, precisamos como primeiro parâmetro uma representação do comprimento do restante da entrada, por exemplo c, de modo que Ackermann (c) seja o comprimento da entrada. Como isso também não é adequado, exigimos como primeiro valor em nossa entrada o parâmetro c, de forma que bb (c) seja sobre o comprimento da entrada, onde bb é a função de castor ocupado. Essa função é incomputável, mas bb (c) certamente existe. Então, o algoritmo é assim:

for (int i=0; i<c; i++) {
    if (input[i] == null) {
        return false;
    }
}
return true;

O objetivo do algoritmo é verificar se, se c é o inverso de bb, se o comprimento da entrada é maior que bb (c).

Se existe uma função computável que cresce mais rapidamente que a função Ackermann, acho que podemos usá-la inversa para criar um algoritmo que responda à sua pergunta em qualquer entrada.

Albert Hendriks
fonte

Definitivamente, existem funções que crescem mais rapidamente que a função Ackermann, como apontado nos comentários (TREE (n)). A parte complicada da questão é construir um algoritmo com um limite de tempo de execução do inverso dessa função. Essa máquina não tem tempo suficiente para calcular o inverso da função em primeiro lugar; portanto, a construção de uma TM que atinja isso não é direta.

Mdxn