¿Las funciones con un crecimiento más lento que el inverso de Ackermann aparecen en los límites de tiempo de ejecución?

Algunos algoritmos complicados ( union-find ) tienen la función inversa de Ackermann casi constante que aparece en la complejidad de tiempo asintótica, y son óptimos en el peor de los casos si se ignora el término de Ackermann inverso casi constante.

¿Hay ejemplos de algoritmos conocidos con tiempos de ejecución que involucren funciones que crecen fundamentalmente más lento que el inverso de Ackermann (por ejemplo, inversos de funciones que no son equivalentes a Ackermann bajo transformaciones polinómicas o exponenciales, etc.), que dan el mejor momento conocido en el peor de los casos? complejidad para resolver el problema subyacente?

reference-request algorithm-analysis time-complexity runtime-analysis usuario2566092
fuente

algoritmos de tiempo? ¿Está preguntando acerca de un problema conocido cuyo algoritmo mejor conocido es

? Primero necesita encontrar una función que crezca "fundamentalmente más rápido" que

, como TREE

, y luego tomar su inverso, ¡y luego encontrar un problema que se ajuste a él!

O (1)

$O(1)$

ω (1)

$\omega(1)$

o (α (n))

$o(\alpha(n))$

A (n)

$A(n)$

(n)

$(n)$

Pål GD

Hay algoritmos arbitrarios creados a partir de la jerarquía de tiempo

thm

@vzn: Cualquier

no es construible en el tiempo (lo que incluye

). Por lo tanto, el teorema de la jerarquía del tiempo no puede usarse aquí.

f (n) = o (n)

$f(n) = o(n)$

α (n)

$\alpha(n)$

mdxn

@mdx me alegra que alguien lo haya señalado, solo te estoy probando un guiño. Sí, últimamente he estado pensando que podría haber una generalización de la jerarquía de tiempo para las funciones sub-

. pero de todos modos el límite

se debe a que un TM construible en el tiempo debe leer toda la entrada, pero ¿estamos diciendo que estos otros algoritmos, por ejemplo, con complejidad de tiempo inversa de Ackermann, no? teniendo problemas para visualizar esto! siento que la pregunta es más sobre la existencia de sub-

idiomas ... ¿podría haber algún tipo de encuesta o descripción en alguna parte ...

o (n)

$o(n)$

o (n)

$o(n)$

o (n)

$o(n)$

vzn

@vzn: El OP realmente necesita aclarar qué modelo de cálculo tienen en mente.

deben definirse en TM de acceso aleatorio (o equivalentes). Al especificar nuestra mecánica, podríamos agregar inadvertidamente demasiada potencia. Incluso puede ser en la medida en que la noción de complejidad computacional no sea fructífera. En los términos más básicos, tendríamos que cambiar nuestra noción de complejidad temporal (que es lo que hace el tiempo de ejecución amortizado) con el riesgo de que tal definición se vuelva muy artificial (lo mismo ocurre con el modelo de cómputo).

DLOGTIME

$\text{DLOGTIME}$

LH

$\text{LH}$

mdxn

Respuestas:

Seth Pettie ideó un algoritmo para calcular el sensibilidad de un árbol de expansión mínimo en el tiempo , mejorando un algoritmo de Tarjan que calcula lo mismo en el tiempo . (Compare esto con el algoritmo Chazelle para calcular el árbol de expansión mínimo $O(m\log \alpha(m,n))$ $O(m\alpha(m,n))$ $O(m\alpha(m,n))$ en sí.) El problema de sensibilidad requiere calcular, para un gráfico dado y un árbol de expansión mínimo dado, cuánto puede cambiar el peso de cada borde sin cambiar el árbol de expansión mínimo.

(Gracias a Tsvi Kopelowitz por esta referencia).

Yuval Filmus
fuente

No sé si el registro inverso de Ackermann es "fundamentalmente más lento" que el inverso de Ackermann, pero este tipo de tiempo de ejecución me pareció sorprendente.

Yuval Filmus

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

templatetypedef
fuente

-1

Cuando Alan Turing descubrió la computadora, solía haber varios modelos para la computadora propuesta. Turing demostró que algunos (3) de estos modelos podían simularse entre sí Y calcular la función de Ackermann, mientras que los otros modelos podían simularse entre sí, pero no la función de Ackermann (por lo que no podían simular el 3). Por lo tanto, estos 3 modelos (Turing Machine, von Neumann y uno que no conozco), fueron elegidos como la arquitectura para una computadora. Esto no significa que la función de Ackermann sea el límite de la computadora, pero supongo que es una ciencia difícil. No conozco ninguna función computable que crezca más rápido que la función de Ackermann.

Ahora, no creo que haya un problema práctico que coincida con su pregunta, pero quizás podamos construir uno. Sin embargo, necesitamos poner restricciones en la entrada. Como no podemos usar O (n), no podemos verificar toda la entrada. De hecho, ni siquiera podemos verificar la longitud de la entrada, ya que sería O (log n). Por lo tanto, necesitamos como primer parámetro una representación de la longitud del resto de la entrada, por ejemplo c tal que Ackermann (c) sea la longitud de la entrada. Como esto tampoco es adecuado, exigimos como primer valor en nuestra entrada el parámetro c, de modo que bb (c) sea aproximadamente la longitud de la entrada, donde bb es la función de castor ocupado. Esta función es incuestionable pero bb (c) ciertamente existe. Entonces, el algoritmo es como:

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

El propósito del algoritmo es verificar que si c es el inverso de bb, si la longitud de entrada es mayor que bb (c).

Si hay una función computable que crece más rápido que la función de Ackermann, creo que podemos usar su inversa para crear un algoritmo que responda a su pregunta en cualquier entrada.

Albert Hendriks
fuente

Definitivamente existen funciones que crecen más rápido que la función de Ackermann como se señala en los comentarios (TREE (n)). La parte difícil de la pregunta es construir un algoritmo con un límite de tiempo de ejecución de la inversa de esa función. Tal máquina no tiene tiempo suficiente para calcular la inversa de la función en primer lugar, por lo que la construcción de una TM que logre esto no es sencilla.

mdxn